A most delightful puzzle

Arrangements, sorting, packing, partitions, critical path analysis, networks, graphs, ...
Post Reply
GraemeMcRae
Posts: 46
Joined: Thu Jul 12, 2007 9:59 pm

A most delightful puzzle

Post by GraemeMcRae »

A tetromino is a four-celled "animal" composed of squares joined on their sides. "One-sided" tetrominoes are considered the same if one can be rotated to make the other, and different otherwise. There are seven one-sided tetrominos: Image, Image, Image, Image, Image, Image, and Image.

There are 37 distinct ways to tile a 4 by 4 square with one-sided tetrominoes, where "distinct" is taken to mean that no two distinct tilings are rotations of one another.

How many distinct tilings are there of a 5 by 5 square with one-sided pentominoes?
Last edited by euler on Tue Sep 04, 2007 8:00 am, edited 2 times in total.
Reason: I've moved this to "Discrete Mathematics" as it's an actual problem, whereas "Suggestion, Help, and FAQ" is more to do with questions/issues relating to the forum.

xenon
Posts: 63
Joined: Wed Sep 20, 2006 7:09 pm

Re: A most delightful puzzle

Post by xenon »

Well, that's a no-brainer of course :).

GraemeMcRae
Posts: 46
Joined: Thu Jul 12, 2007 9:59 pm

Re: A most delightful puzzle

Post by GraemeMcRae »

xenon wrote:Well, that's a no-brainer of course :).
Why do you say that?

xenon
Posts: 63
Joined: Wed Sep 20, 2006 7:09 pm

Re: A most delightful puzzle

Post by xenon »

Sorry, I missed the word 'pentominos' :oops:
(It was too early this morning)

GraemeMcRae
Posts: 46
Joined: Thu Jul 12, 2007 9:59 pm

Re: A most delightful puzzle

Post by GraemeMcRae »

Ah! Yes, a checkerboard argument quickly smashes any hope of tiling an odd-size square with even-sized polyominoes!

The puzzle is motivated, as you may have guessed, by many hours of playing the Nintendo 64 game called "New Tetris". There are eight ways to tile a 4-by-4 square with 4 identical Tetris pieces (one-sided tetrominos) and 29 other ways to tile the square. Using identical Tetris pieces to make a square gives you a "golden square", worth lots of points, and using non-identical Tetris pieces gives you a "silver square", worth a good number of points as well. Having a good working knowledge of all these ways to pack Tetris pieces helps you improve your score.

I was surprised by how hard it was to convince myself that I had found all the 37 ways to tile a 4x4 square. Also, as far as I can see, OEIS doesn't contain the sequence of the numbers of such n-tilings for n=1, 2, 3, 4, ... This sequence is 1, 1, 3, 37, ... So I expect it will take someone a good length of time to write the program to find the answer for n=5.

User avatar
ed_r
Posts: 1009
Joined: Sun Jul 29, 2007 10:57 am

Re: A most delightful puzzle

Post by ed_r »

I make it 1018.

For n=6, I get 113185.
For n=7, I get 10929277. (correction: 39691061)

My program can't get further than that in reasonable time.
Last edited by ed_r on Wed Sep 05, 2007 7:09 am, edited 1 time in total.
!647 = &8FDF4C

GraemeMcRae
Posts: 46
Joined: Thu Jul 12, 2007 9:59 pm

Re: A most delightful puzzle

Post by GraemeMcRae »

Ed_r, Yes, I got the same number you did for n=5 as well, and running the program overnight I verified n=6, but my program bogs down for larger n. It works by trying each valid "positioning" (a piece in one of the possible positions) for the first piece, and for each one, it tries each valid positioning of the second piece, etc. "Valid" means leaving no holes that aren't a multiple of n in size. Then for each valid positioning of all n pieces (a board position), I check all 4 rotations the whole board to see if I've already seen this board positioning.

I'm working on ways to speed up my program. For example, to position the last piece, I already know exactly what hole it fits into, but I don't have an efficient way of finding that piece. What ideas helped you speed up your program?

User avatar
ed_r
Posts: 1009
Joined: Sun Jul 29, 2007 10:57 am

Re: A most delightful puzzle

Post by ed_r »

Graeme, I'm glad that you have verified my results for N=5,6. N=7 is much harder (~10000 sec, compared to ~5 sec when N=6, on my computer). N=8 will need some new ideas.

My attack on the problem is a pretty straightforward depth-first search.

I start by tabulating all rotated pieces (19 rotated pieces for N=4). For each piece, I tabulate all translations within the NxN search area, storing the resultant shifted/rotated piece as a bitmask (113 bitmasks for N=4). The positions in the bitmask come from scanning the NxN search area with diagonal stripes (this scan order does not seem to be very important, though), such that for N=4 we have, for example:

Code: Select all

Bit positions    Shifted piece      Bitmask for shifted piece
   +----+        (e.g.) +----+
   |0136|               |....|      Position: fedc ba98 7654 3210
   |247a|               |..#.|           Set? nnYn YnnY Ynnn nnnn
   |58bd|               |.###|         Value: 0010 1001 1000 0000 (binary)
   |9cef|               |....|                           = 0x2980 (hex)
   +----+               +----+
The bitmasks are split into N2 lists, such that the kth list - call it List(k) - consists of those bitmasks whose rightmost '1' is in position k. The depth-first search the proceeds roughly according to the following pseudocoded recursion:

Code: Select all

search(m) {   // m = bitmask of cells filled so far
  let k = position of rightmost '0' in m
  for each bitmask, b, in List(k) {
    if (b AND m == 0) {
      search(m OR b)
    }
  }
}
For N=4, this gives C=117 solutions, which is obviously wrong because we've failed to eliminate rotations.

However, all is not lost. Let ...
  • C180 = nr solutions with (at least) 180-degree symmetry;
  • C90 = nr solutions with 90-degree symmetry.
... then a little thought shows that the correct answer is [frac](C - C180),4[/frac] + [frac](C180 - C90),2[/frac] + C90 . Skipping ahead a little, for N=4 this works out as [frac](117 - 21),4[/frac] + [frac](21 - 5),2[/frac] + 5 = 24 + 8 + 5 = 37.

I've got a pile of housework to do now :( but hopefully that's enough info to be getting on with. I'll describe the calculations for C180 and C90 when I have more time, if there's interest.
!647 = &8FDF4C

GraemeMcRae
Posts: 46
Joined: Thu Jul 12, 2007 9:59 pm

Re: A most delightful puzzle

Post by GraemeMcRae »

It seems we've done the same sorts of thing. Your 113 bitmasks correspond to my 113 "positionings" for n=4. I use one bitmask for each row of the table, though, so that I can accommodate n's larger then 5 without exceeding my largest integer (32 bits).

One thing I do that I don't see you doing is "pruning" my depth-first search to eliminate configurations in which the first two positionings leave a "hole" that is not a multiple of n in size.

One thing you do that I've been thinking about doing is sorting my "positionings" (bitmasks) to make it quicker to find a particular piece. In the midst of my search, once I've placed n-1 of the pieces, and the position is valid, then there is a single hole of n squares, which fits the last remaining n-polyomino. It would speed up my program considerably if I could zero in quickly on that exact polyomino.

Another thing I've been thinking about doing is making lists of 2 valid positinings -- sort of like pairs of pieces "glued" together (although there could be some space between them). For the tough n=8 case, 2 pairs of pieces would be matched up in valid positionings to make "clumps" of 4 pieces "glued" together. Then instead of adding pieces a few at a time, the clumps would simply be matched up to one another.

User avatar
ed_r
Posts: 1009
Joined: Sun Jul 29, 2007 10:57 am

Re: A most delightful puzzle

Post by ed_r »

One thing I did try was to maintain a hash table of all patterns that can be made with k pieces (k=1,2,3,...) and a tag against each pattern that says how many ways that could be achieved. If there are 100 ways to make a particular pattern with 3 pieces (say) then this means you only need to try extending one of those, then multiply by 100 at the end, rather than recursively extend each and end up with the same result 100 times.

A reasonable idea in theory, perhaps, but it ate up too much memory when n=7. If I'd pruned the patterns, e.g. checked for unfillable holes, then the memory footprint might've been reasonable for n=7 but it would still be way too large for n=8. (Pruning is no good for my pure DFS attack, though, because it adds too much computational overhead in general.)

btw, I just realised that a silly typo in my code (used 1<<i instead of 1ull<<i in a couple of places) means my n=7 result is wrong. I'll post a correction in the morning, having just set the corrected 10000-second attack running now. (Edit: made that correction now.)
!647 = &8FDF4C

Post Reply