Optimize tiling for a 50x50 grid

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

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

Optimize tiling for a 50x50 grid

Postby Cradarc » Wed Mar 02, 2016 11:14 pm UTC

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.

User avatar
jaap
Posts: 2085
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Optimize tiling for a 50x50 grid

Postby jaap » Thu Mar 03, 2016 8:51 am UTC

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

Postby curiosityspoon » Thu Mar 03, 2016 6:38 pm UTC

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.

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

Re: Optimize tiling for a 50x50 grid

Postby Cradarc » Thu Mar 03, 2016 9:08 pm UTC

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.

User avatar
jaap
Posts: 2085
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Optimize tiling for a 50x50 grid

Postby jaap » Fri Mar 04, 2016 6:36 am UTC

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


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

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

Re: Optimize tiling for a 50x50 grid

Postby Cradarc » Fri Mar 04, 2016 9:04 am UTC

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.

User avatar
jaap
Posts: 2085
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Optimize tiling for a 50x50 grid

Postby jaap » Fri Mar 04, 2016 9:45 am UTC

Cradarc wrote: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?

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

Postby Poker » Fri Mar 04, 2016 2:50 pm UTC

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:
Image


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


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 7 guests