A most delightful puzzle

 Posts: 46
 Joined: Thu Jul 12, 2007 9:59 pm
A most delightful puzzle
A tetromino is a fourcelled "animal" composed of squares joined on their sides. "Onesided" tetrominoes are considered the same if one can be rotated to make the other, and different otherwise. There are seven onesided tetrominos: , , , , , , and .
There are 37 distinct ways to tile a 4 by 4 square with onesided 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 onesided pentominoes?
There are 37 distinct ways to tile a 4 by 4 square with onesided 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 onesided 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.
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.
Re: A most delightful puzzle
Well, that's a nobrainer of course .

 Posts: 46
 Joined: Thu Jul 12, 2007 9:59 pm
Re: A most delightful puzzle
Why do you say that?xenon wrote:Well, that's a nobrainer of course .
Re: A most delightful puzzle
Sorry, I missed the word 'pentominos'
(It was too early this morning)
(It was too early this morning)

 Posts: 46
 Joined: Thu Jul 12, 2007 9:59 pm
Re: A most delightful puzzle
Ah! Yes, a checkerboard argument quickly smashes any hope of tiling an oddsize square with evensized 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 4by4 square with 4 identical Tetris pieces (onesided 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 nonidentical 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 ntilings 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.
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 4by4 square with 4 identical Tetris pieces (onesided 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 nonidentical 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 ntilings 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.
Re: A most delightful puzzle
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.
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

 Posts: 46
 Joined: Thu Jul 12, 2007 9:59 pm
Re: A most delightful puzzle
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?
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?
Re: A most delightful puzzle
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 depthfirst 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:
The bitmasks are split into N^{2} lists, such that the k^{th} list  call it List(k)  consists of those bitmasks whose rightmost '1' is in position k. The depthfirst search the proceeds roughly according to the following pseudocoded recursion:
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 ...
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 C_{180} and C_{90} when I have more time, if there's interest.
My attack on the problem is a pretty straightforward depthfirst 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)
++ ++
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)
}
}
}
However, all is not lost. Let ...
 C_{180} = nr solutions with (at least) 180degree symmetry;
 C_{90} = nr solutions with 90degree symmetry.
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 C_{180} and C_{90} when I have more time, if there's interest.
!647 = &8FDF4C

 Posts: 46
 Joined: Thu Jul 12, 2007 9:59 pm
Re: A most delightful puzzle
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 depthfirst 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 n1 of the pieces, and the position is valid, then there is a single hole of n squares, which fits the last remaining npolyomino. 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.
One thing I do that I don't see you doing is "pruning" my depthfirst 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 n1 of the pieces, and the position is valid, then there is a single hole of n squares, which fits the last remaining npolyomino. 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.
Re: A most delightful puzzle
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 10000second attack running now. (Edit: made that correction now.)
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 10000second attack running now. (Edit: made that correction now.)
!647 = &8FDF4C