20080409, 02:49  #1 
May 2004
New York City
2^{3}×23^{2} Posts 
Jigsaw Puzzles
Define a "jigsaw puzzle" to be simply an MxN grid of squares
divided into K interlocking polyomino pieces. Call a jigsaw puzzle "standard" if M=N=K and all the pieces are distinguishable, i.e. if it's an NxN grid with N different interlocking polyomino pieces. For example, there is obviously only one 1x1 standard jigsaw puzzle, and also there is only one 2x2 standard puzzle: AA AB Some 3x3 standard puzzles are: AAA ABB ABC and AAA BAC BBC The question is: how may standard jigsaw puzzles are there for N = 1,2,3,4,5,6 and 7? (If you can solve for higher N, say 8,9, and 10, great.) 
20080409, 15:17  #2 
"Lucan"
Dec 2006
England
2×3×13×83 Posts 
Can the polyominoes have different numbers of squares?
Does a polyomino have to be connected by edges? What does your ABC notaion refer to? Are they rotatable/reflectable? Last fiddled with by davieddy on 20080409 at 15:19 
20080409, 16:33  #3  
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
2·2,897 Posts 
Quote:
another is: AAA BCA BBA 

20080409, 16:49  #4 
Jan 2005
Transdniestr
503 Posts 
Or:
AAA ABA CCA Can I assume that if: AA BA is part of the distinct count, then AA AB and BB BA would not be counted as they would be equivalent to the first one? Last fiddled with by grandpascorpion on 20080409 at 16:50 
20080409, 17:38  #5 
Jan 2005
Transdniestr
111110111_{2} Posts 
Distinct 3x3 solutions accounting for reflection/ rotation and labeling by letter
Hopefully, it's complete Code:
4,3,2 AAA AAA AAA BBB AAA ACC ABC ABB AAA BAC BBB BBC CCB ACC BBC 5,3,1 AAA AAA AAA AAA AAA AAA AAA BBB BBB AAC ACA ABA ABB ABB ACB ABC AAA AAA BBB BBB BBC ACB ABC ABB ABB ACA AAC 6,2,1 AAA AAA AAA AAA AAA ABB ABB BBA AAC ACA AAA AAB ABA AAA AAA AAA ABB ABB BBC ACB ABC ACA AAC AAC Solutions with duplicate polyominoes: 3,3,3 AAA BAA BBB BBA CCC CCC 5,2,2 AAA BAA AAA AAA ABB AAC BAC ABB ABC AAA BBC AAC ACC ABC ACC 7,1,1 AAA AAB ABA ABA AAA BAA AAA AAB AAA AAA ACA ABA AAA BAA AAC AAC ACA AAA AAC AAC AAC Last fiddled with by grandpascorpion on 20080409 at 18:09 Reason: add duplicates 
20080409, 17:46  #6 
May 2004
New York City
2^{3}·23^{2} Posts 
I could have been clearer.
The polyominoes can have any number of squares, as long as they fit in an NxN grid. They must be connected by edges (not just corners). Symmetric polyominoes are not considered different. Symmetries (rotations, reflections) of the whole puzzle should be not be counted separately. In the ABC symbolism, each letter represents a square in the grid, with a polyomino represented by all the squares with the same letter. The letters are just place holders, so permutations of the letters don't count as extra jigsaws. And on further reflection, I think N=7 and even N=6 may be too computationally costly to solve easily. /* edit */ I see that the 3x3 solution looks like it interpreted all this addendum correctly, except that it includes a few symmetries that I didn't intend counted. /* endedit */ Last fiddled with by davar55 on 20080409 at 17:52 
20080409, 17:53  #7 
"Ben"
Feb 2007
3,361 Posts 

20080409, 17:59  #8 
Jan 2005
Transdniestr
503 Posts 
True, I thought they had to be different sizes.
Actually, AAA BBB CCC AAB ABB CCC would be valid too. I'll edit the post 
20080409, 18:02  #9  
"Ben"
Feb 2007
D21_{16} Posts 
Quote:
So mine is out, but your second 3,3,3 example works. 

20080409, 18:33  #10 
Jan 2005
Transdniestr
503 Posts 
But the 2nd one has two "L"s, so that would be out, too.

20080409, 18:48  #11 
Jan 2005
Transdniestr
503 Posts 
19 Classes for 4x4 squares (where the polyominoes are distinct shapes):
10,3,2,1 9,4,2,1 9,3,3,1 8,5,2,1 8,4,3,1 8,3,3,2 7,6,2,1 7,5,3,1 7,4,3,2 7,4,4,1 6,6,2,2 6,5,3,2 6,5,4,1 6,4,4,2 6,4,3,3 5,5,5,1 5,5,4,2 5,5,3,3 5,4,4,3 4,4,4,4 isn't possible. So, the class count is really a partition problem. Last fiddled with by grandpascorpion on 20080409 at 18:56 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
The Railroad Puzzles  Wacky  Puzzles  45  20130418 22:26 
logic puzzles  science_man_88  Puzzles  0  20110328 17:31 
Some puzzles  fetofs  Puzzles  32  20051026 18:32 
Circle Puzzles 1  mfgoode  Puzzles  18  20050711 11:51 
Puzzles without solutions  Orgasmic Troll  Puzzles  12  20030716 09:36 