## Optimize tiling for a 50x50 grid

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

Posts: 455
Joined: Fri Nov 28, 2014 11:30 pm UTC

### Optimize tiling for a 50x50 grid

You are given a rectangular grid with dimensions 50 x 50 and a supply of rectangular tiles of various sizes. Your goal is to earn as many points as possible by placing tiles on the grid.

Rules:
1. Tiles cannot overlap or extend outside the grid.
2. Tiles must line up with the grid lines, so they can only be rotated by 90 degrees.
3. A M x N tile placed on the grid will give you P = NM - (N+M) points (ie. area - semiperimeter)
4. For every tile dimension that is not a factor of 50, you earn 2 bonus point (for placing that tile). So a M x N tile will give you P+4 points if neither N nor M is a factor of 50.

You have the following tiles:

Code: Select all

`(length x width): Quantity(19 x 19): 1(13 x 7): 1(11 x 11): 1(10 x 8): 1(9 x 7): 2(8 x 6): 8(8 x 5): 7(7 x 7): 4(7 x 6): 6(7 x 5): 1(6 x 4): 3(5 x 4): 8(5 x 3): 1(4 x 4): 10(5 x 5): unlimited`

TIP: You can gauge your "efficiency" by taking the ratio of your total points over 2500. For example, using only 5x5 tiles, you will get 1500 points which yields 1500/2500 = 0.6 efficiency.
Last edited by Cradarc on Thu Mar 03, 2016 9:08 pm UTC, edited 1 time in total.
This is a block of text that can be added to posts you make. There is a 300 character limit.

jaap
Posts: 2091
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

### Re: Optimize tiling for a 50x50 grid

Cradarc wrote:3. A M x N tile placed on the grid will give you P = NM - 0.5*(N+M) points (ie. area - semiperimeter)

That's not the semiperimeter, it's a quarter of the perimeter.

curiosityspoon
Posts: 35
Joined: Wed Sep 24, 2014 5:01 pm UTC

### Re: Optimize tiling for a 50x50 grid

A 5x5 tile is worth 20, so filling the board with them scores 2000, not 1500. This makes the per-square efficiency 0.8, compared to the 1 point per square of the most efficient tile, the 4x4.

Posts: 455
Joined: Fri Nov 28, 2014 11:30 pm UTC

### Re: Optimize tiling for a 50x50 grid

jaap wrote:
Cradarc wrote:3. A M x N tile placed on the grid will give you P = NM - 0.5*(N+M) points (ie. area - semiperimeter)

That's not the semiperimeter, it's a quarter of the perimeter.

Sorry, brain fart. It should be fixed now.
This is a block of text that can be added to posts you make. There is a 300 character limit.

jaap
Posts: 2091
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

### Re: Optimize tiling for a 50x50 grid

Here's a solution using six 5x5 tiles and all of the others. Only 17 squares are left empty.
Spoiler:

Edit:
Here's one that fills it completely. Nine 5x5's are used.
Spoiler:

Posts: 455
Joined: Fri Nov 28, 2014 11:30 pm UTC

### Re: Optimize tiling for a 50x50 grid

Impressive Jaap!
I only managed to get one with 17 squares left with graph paper. I didn't think it was possible to fill all 2500. If you ran a computer algorithm, do you mind sharing the code?
This is a block of text that can be added to posts you make. There is a 300 character limit.

jaap
Posts: 2091
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

### Re: Optimize tiling for a 50x50 grid

I only managed to get one with 17 squares left with graph paper. I didn't think it was possible to fill all 2500. If you ran a computer algorithm, do you mind sharing the code?

It's my PolyForm Puzzle Solver Java applet on my puzzle site. If you can't get it to run in your browser, you can download it and run it standalone instead.
http://www.jaapsch.net/puzzles/polysolver.htm

Poker
Posts: 60
Joined: Fri Jun 15, 2007 2:33 am UTC
Location: Multiple Places (only one now that you read this...)

### Re: Optimize tiling for a 50x50 grid

Nice job filling in the whole grid. If I'm doing the math right, that's 1934 points.

On the other hand, there's no penalty for leaving squares unfilled.

Here's my solution: it leaves 2 squares unfilled and scores 1942 points. I used 8 5x5 tiles and discarded a 5x4 and a 5x3.

Spoiler:

Somebody check my work - unless I made a mistake, some dynamic programming should prove that 1942 is the maximum.