Jigsaw Puzzles

[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.)

[davieddy]

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?

[henryzz]

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

[grandpascorpion]

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?

[grandpascorpion]

Distinct 3x3 solutions accounting for reflection/ rotation and labeling by letter
Hopefully, it's complete

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

[davar55]

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 */

[bsquared]

Originally Posted by grandpascorpion

Distinct 3x3 solutions accounting for reflection/ rotation and labeling by letter
Hopefully, it's complete

What about the 3,3,3 case?

 
AAA
BBB
CCC

[grandpascorpion]

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

[bsquared]

Originally Posted by davar55

Call a jigsaw puzzle "standard" if M=N=K and all the pieces are distinguishable

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.

[grandpascorpion]

But the 2nd one has two "L"s, so that would be out, too.

[grandpascorpion]

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.