mersenneforum.org Jigsaw Puzzles
 Register FAQ Search Today's Posts Mark Forums Read

 2008-04-09, 02:49 #1 davar55     May 2004 New York City 23×232 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.)
 2008-04-09, 15:17 #2 davieddy     "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 2008-04-09 at 15:19
2008-04-09, 16:33   #3
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT/BST)

2·2,897 Posts

Quote:
 Originally Posted by davar55 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.)
i am presuming u have not posted all possibilities for 3x3
another is:
AAA
BCA
BBA

 2008-04-09, 16:49 #4 grandpascorpion     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 2008-04-09 at 16:50
 2008-04-09, 17:38 #5 grandpascorpion     Jan 2005 Transdniestr 1111101112 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 2008-04-09 at 18:09 Reason: add duplicates
 2008-04-09, 17:46 #6 davar55     May 2004 New York City 23·232 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 2008-04-09 at 17:52
2008-04-09, 17:53   #7
bsquared

"Ben"
Feb 2007

3,361 Posts

Quote:
 Originally Posted by grandpascorpion Distinct 3x3 solutions accounting for reflection/ rotation and labeling by letter Hopefully, it's complete
Code:

AAA
BBB
CCC

 2008-04-09, 17:59 #8 grandpascorpion     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
2008-04-09, 18:02   #9
bsquared

"Ben"
Feb 2007

D2116 Posts

Quote:
 Originally Posted by davar55 Call a jigsaw puzzle "standard" if M=N=K and all the pieces are distinguishable
Quote:
 Originally Posted by grandpascorpion True, I thought they had to be different sizes.
Now that I re-read the problem statement, I think you're right. That is what's meant by "distinguishable".

So mine is out, but your second 3,3,3 example works.

 2008-04-09, 18:33 #10 grandpascorpion     Jan 2005 Transdniestr 503 Posts But the 2nd one has two "L"s, so that would be out, too.
 2008-04-09, 18:48 #11 grandpascorpion     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 2008-04-09 at 18:56

 Similar Threads Thread Thread Starter Forum Replies Last Post Wacky Puzzles 45 2013-04-18 22:26 science_man_88 Puzzles 0 2011-03-28 17:31 fetofs Puzzles 32 2005-10-26 18:32 mfgoode Puzzles 18 2005-07-11 11:51 Orgasmic Troll Puzzles 12 2003-07-16 09:36

All times are UTC. The time now is 14:02.

Wed Jan 20 14:02:16 UTC 2021 up 48 days, 10:13, 0 users, load averages: 4.31, 4.24, 4.25

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.