mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2008-04-09, 02:49   #1
davar55
 
davar55's Avatar
 
May 2004
New York City

23×232 Posts
Default 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.)
davar55 is offline   Reply With Quote
Old 2008-04-09, 15:17   #2
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

2×3×13×83 Posts
Default

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
davieddy is offline   Reply With Quote
Old 2008-04-09, 16:33   #3
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2·2,897 Posts
Default

Quote:
Originally Posted by davar55 View Post
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
henryzz is online now   Reply With Quote
Old 2008-04-09, 16:49   #4
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

503 Posts
Default

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
grandpascorpion is offline   Reply With Quote
Old 2008-04-09, 17:38   #5
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

1111101112 Posts
Default

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
grandpascorpion is offline   Reply With Quote
Old 2008-04-09, 17:46   #6
davar55
 
davar55's Avatar
 
May 2004
New York City

23·232 Posts
Default

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
davar55 is offline   Reply With Quote
Old 2008-04-09, 17:53   #7
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

3,361 Posts
Default

Quote:
Originally Posted by grandpascorpion View Post
Distinct 3x3 solutions accounting for reflection/ rotation and labeling by letter
Hopefully, it's complete
What about the 3,3,3 case?
Code:
 
AAA
BBB
CCC
bsquared is offline   Reply With Quote
Old 2008-04-09, 17:59   #8
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

503 Posts
Default

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
grandpascorpion is offline   Reply With Quote
Old 2008-04-09, 18:02   #9
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

D2116 Posts
Default

Quote:
Originally Posted by davar55 View Post
Call a jigsaw puzzle "standard" if M=N=K and all the pieces are distinguishable
Quote:
Originally Posted by grandpascorpion View Post
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.
bsquared is offline   Reply With Quote
Old 2008-04-09, 18:33   #10
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

503 Posts
Default

But the 2nd one has two "L"s, so that would be out, too.
grandpascorpion is offline   Reply With Quote
Old 2008-04-09, 18:48   #11
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

503 Posts
Default

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
grandpascorpion is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
The Railroad Puzzles Wacky Puzzles 45 2013-04-18 22:26
logic puzzles science_man_88 Puzzles 0 2011-03-28 17:31
Some puzzles fetofs Puzzles 32 2005-10-26 18:32
Circle Puzzles 1 mfgoode Puzzles 18 2005-07-11 11:51
Puzzles without solutions 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

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.