# cheapskate jigsaw inc

Jigsaw puzzles are awesome and making them is an easy way to get rich. So I bought a cutting machine to make puzzles. Unfortunately I could only afford the cheapest machine available. All pieces are arranged in the standard rectangular pattern, no fancy shapes or arrangements.

Additionally the machine can only do a single shape for the tap and the blank. That means any two pieces with a tap and a blank fit together.

I still want to have my puzzles a unique correct solution. So in spite of the individual pieces fitting together in lots of ways there should be only one way to arrange all pieces into a rectangle.

Question: What is the biggest puzzle in terms of number of pieces I can make?

Here are two examples of puzzles I could make with the machine. Any individual piece can be described by listing the four sides in clockwise order. Each can be a (s)ide, a (t)ap or a (b)lank.

Puzzle A consists of the four pieces (s,s,t,t), (s,s,t,b), (s,s,b,t) and (s,s,b,b). This can be assembled as a 2 by 2 puzzle in a unique way (up to rotation). This is a good puzzle.

Puzzle B consists of the four pieces (s,s,t,t), (s,s,t,b), (s,s,t,b) and (s,s,b,b). This can be assembled as a 2 by 2 puzzle in two distinct ways. So there is no unique solution and I don't want that.

PS: This can be solved with pen and paper, no computer required. If someone wants to make helpful pictures feel free to edit.

Edit in response to comments: If a piece can be rotated in place the picture would still be off so that would count as distinct ways to assemble. Sides are only on the boundary, not inside the puzzle.

• I suppose it is not OK if a piece can be rotated ? So (btbt) cannot be used? Feb 3, 2022 at 12:23
• Can flat sides appear between 2 pieces? Feb 3, 2022 at 12:24

The biggest puzzle is 2x2.

I wrote code to consider both orientations for each internal edge of a puzzle of fixed dimensions. For example, the 5x3 puzzle has 22 internal edges, so 2^22 configurations. Configurations with duplicate/invalid pieces were discarded. To avoid finding two solutions that are rotations of each other, sstt was forced to be in the left column (and also in the top row for square puzzles).

Curiously, all tilesets (except 2x2) have an even number of solutions.

Nx2 doesn't work for N>2 because you can always rotate just the 4 corner pieces.

2x2
{ssbb ssbt sstb sstt}:

3x2
{sbbt ssbb ssbt sttb sstb sstt}:

{stbb ssbb sbtt ssbt sstb sstt}:

4x2

3x3

4x3

5x3

Partial answer, providing an upper bound

There are 4 possible corner pieces and 4 corners to fill, so all possible corner pieces must be used. There are 8 possible edge pieces, so the perimeter of our completed puzzle cannot exceed 16, which limits the possible sizes to $$4×4,3×5,2×6,3×4,2×5,3×3,2×4,2×3,2×2$$. (We can easily exclude $$1×n$$ puzzles.)

We will now show that the rectangle cannot have perimeter 16.

It is easy to show that the subpattern formed by corner pieces is always distinct up to rotation from its reflection except in square puzzles where the only exceptions place the two-tap and two-blank pieces at opposite corners. If the perimeter is 16 all 8 possible edge pieces must be used, but reflection forms an automorphism of this group; all interior pieces are also reflection-symmetric. A perimeter-16 rectangle thus cannot possibly have a unique solution from this reflection argument, except perhaps in the 4×4 diagonal-symmetric case. That exception does not lead to a valid puzzle either, since the two interior pieces not on the line of symmetry would have to be identical. Hence we eliminate the $$4×4,3×5,2×6$$ cases.

• Which reflection do you mean? For rectangles you can reflect along a horizontal or along a vertical, for squares you reflect along the diagonals as well. Feb 3, 2022 at 18:59
• @quarague All of them. Feb 3, 2022 at 19:04

There are only so many types of pieces, and we can only use one of each to have a unique solution. Starting with some (lol) edge cases:

ssss is possible, but would be a 1-piece puzzle.

sssb, ssst, stst, sbsb, and stsb could make a 1x5 puzzle, which improves on the 2x2 in the original post. (sbst is equivalent to stsb by rotation.)

Now that that's out of the way, we have:

corner pieces: sstt, sstb, ssbb, ssbt. There are four, which is good, since four is all we need.

edge pieces: sttt, sttb, stbt, stbb, sbtt, sbtb, sbbt, sbbb. There are eight, which is enough to make a 4x4, 3x5, or 2x6 puzzle, giving us a theoretical maximum of 16 pieces.

internal pieces: tttb, ttbb, tbbb. (There is also tttt, tbtb, and bbbb, but as pointed out in comments, those are all rotationally symmetrical, so would not provide a unique solution.) There are only three, so we can't fill in the 4x4, but we can fill in the 3x5.

With these pieces, the largest puzzle we can make is a

3x5, consisting of 15 pieces:

• bbbb and tttt are both rotationally symmetrical, so cannot be used.
– fljx
Feb 3, 2022 at 15:35
• @fljx d'oh. of course they are. updated accordingly. Feb 3, 2022 at 15:57
• The question asks for the largest set of pieces that have a unique solution. That set of fifteen has multiple solutions - e.g. rotate the centre three pieces 180 degrees as a group.
– fljx
Feb 3, 2022 at 16:07
• This looks pretty good but @fljx comment is correct. This jigsaw still admits multiple solutions. Nice picture by the way. Feb 3, 2022 at 19:00
• @quarague but wouldn't those still be the same 15 pieces that could then be rearranged back into this orientation? Feb 5, 2022 at 23:05

## Introduction

I learned how to solve puzzles from my ma: Do the edges first.

Accordingly, I start solutions with the perimeter. The perimeter is simple: each piece needs to have opposite parity from both its neighbors. Addressing the internal structure quickly gets tougher. This deceptively straightforward puzzle puzzle blooms into a deep and intriguing challenge.

My answer is quite long. Starting from pieces and perimeters, I prove 1-row, 2-row, and 3-row cases. I've been as concise as I know how, but there are many steps for many cases. I believe my proofs are complete. I'd be delighted for any corrections, compeletions, or streamlining suggestions.

See the Conclusion for a quick summary of my results.

## Preliminary: The 1-Row Puzzle

The 1-Row Puzzle is easy. Still, it presents some useful concepts, so I'm including it as a preliminary case.

Notation. Each piece is represented by 2 characters: 1 or 0 indicates the parity of a face, and a bracket represents an end face. Since we're looking at 1-row puzzles, the top and bottom of each piece are assumed to be side faces.

List of All Pieces. With 3 options for 2 positions there are 3 x 3 combinations. There are 3 pairs that are equivalent under rotation. Therefore there are 6 unique pieces:

 1. []
2. 00 -- this rotates, so is excluded
3. 11 -- this rotates, so is excluded
4. [0 (rotated: 0])
5. [1 (rotated: 1])
6. 01 (rotated: 10)


Solutions. Adjacent faces must have opposite parity. The solutions are small enough to be self-explanatory.

1-Piece solution

[]

2-Piece solution

[0 1]

3-Piece solution

[0 10 1]

4-Piece solution. None.

## Notation

The original post poses the question: "What is the biggest puzzle in terms of number of pieces I can make?"

Therefore, our solution must be in terms of a set of pieces. Arrangements can help prove or disprove uniqueness, but are not an actual solution. A counterexample can be shown with two or more valid arrangements for a specific set of pieces. Arguments can show that an arrangement is possible or impossible.

Corner and side pieces have exactly two neighbors. Adjoining pieces must have opposite parity (described in the original post as tap and blank).

I represent parity as 1s and 0s to simplify calculations. Sometimes I use * or ? to represent parity we don't care about or don't know. I may refer to a piece by its label (e.g. "A" or "w") or simply by its parity ("00").

The perimeter and individual pieces are always read clockwise.

## Puzzle Pieces

List of All Pieces.

1. There are exactly 4 corner pieces
2. There are exactly 8 side pieces -- I organize them in pairs which differ only in internal face parity
3. There are exactly 3 internal pieces

Corners. With each connecting with two neighbors, there are exactly 4 different corner pieces.

Labels: A, B, C, D.

 A. 00
B. 01
C. 10
D. 11


Sides. With two neighbor faces and one internal face, there are 2x2x2 distinct pieces. It's often helpful to pair them accordint to the lef and right parity, since the internal face does not affect constrcution of the perimeter. Labels: w, x, y, z

 1. w: 00 {w0, w1}
2. x: 01 {x0, x1}
3. y: 10 {y0, y1}
4. z: 11 {z0, z1}


Internal Labels: 𝛼, 𝛽, 𝛾

 1. 𝛼: (0001)
2. 𝛽: (1110)
3. 𝛾: (0011)


## Feasible Layouts

No larger layouts are possible because there are only 8 side pieces. The 4x4 layout above is not possible because there are only 3 internal pieces.

### 2x2 Puzzle

Claim. There is only one 2x2 solution:

Proof.

B (01) and C (10) are incompatible; they can never be neighbors. Thus, there is only one 2x2 solution. See Diagram Below. QED

### 2-Row Puzzles

Claim. The 2x2 solution is the only 2-row solution

Proof.

Since B and C can never be neighbors, there are only two possible "bookend" configurations for the ends of a 2-row puzzle.

The Diagram shows how the horizontal bookends and the vertical bookends present the same parity structure (00 and 11) to any candidate pieces. That means if a combination of pieces works with one set of bookends, you can remove the book ends, reassemble them into the other bookends. They will fit the original combination of pieces, giving two arrangements for the same set of pieces.
QED

## 3-Row Puzzles

### 3x3 Puzzle

#### Proof.

Up to rotation of the entire puzzle, there are 3! permutations of corners. This roster of 6 frameworks gives all possible layouts. Corner parity forces selection of side pieces (up to pairs w, x, y, z). See Diagram 1: Roster of Permutations.

Their structure lets us analyze them in two groups -- Group 1: Permutations 1 and 2 (two pairs of sides), and Group 2: Permutations 3, 4, 5, and 6 (no paired sides).

#### Group 1.

Having two pairs of sides means the internal piece must have two of each parity, which makes 𝛾 the only candidate. There are 4 ways parity can be selected. Diagram 2 lays out candidate solutions for Permutation 1. The first two cases have like parity adjoining, which allows 𝛾 to fit as the internal piece. Transposing the x-pair and transposing the y-pair in effect rotates the 𝛾-piece. The second two cases show that any candidate internal piece is invalid because it would allow rotation.
The identical argument rules out Permutation 2, {w0, w1, z0, z1}.

#### Group 2.

Permutations 3, 4, 5, and 6 have one each of w, x, y, and z (no paired sides). That means any of the 2^4 parity combinations can be selected. However, the problem space is constrained because the only candidate internal pieces are 𝛼, 𝛽, and 𝛾.

Permutations 3 and 5 are related by horizontal reflection. Permutations 4 and 6 are related by horizontal reflection. These reflections are executed by permuting the corners and sides as indicated in Diagram 3, below. These reflections are represented as rotations of pieces 𝛼, 𝛽, and 𝛾.

Any set of pieces that fulfills this framework can be rearranged into at least one other arrangement, Therefore, none of these permutations represents any solution.

Group 1 and Group 2 represent all possible arrangements for the 3x3 puzzle. The arguments above show that any set of pieces in Group 1 or Group 2 that has one arrangement has at least on other arrangement. Therefore, there are no solutions for the 3x3 puzzle.

QED

## 3x4 Puzzle

There are 6 faces between the perimeter and the internal pieces. For internal pieces, we can have 𝛼 and 𝛽 (giving 3 faces of one parity and 3 of the other), or 𝛼 and 𝛾 (or 𝛽 and 𝛾) (giving 2 faces of one parity and 4 of the other). We can handle these groups separately because rotating or permuting any pieces cannot change the number of faces of each parity.

### Group 1: 𝛼 + 𝛽

By rotating individually, 𝛼 + 𝛽 can give every parity combination.

In the perimeter there must be at least on pair from w, x, y, z. Such a pair can be transposed in the perimeter because they have the same left-hand and right-hand parity. This may change the pattern of the parity, but can't change count of 3 of each parity. Thus, every member of this Group 1 has at least a transpose partner and therefore is not unique.

### Group 2: 𝛼+𝛾 or 𝛽+𝛾.

The 15 configurations of 𝛽+𝛾 are shown in the diagram. Two combinations are invalid, and marked in orange. One configuration remains unchanged with rotation of its pieces. The other 12 each have a partner where the rotation of a piece gives the same configuration as its partner.

That means, no matter what perimeter we have, the center pieces can be rotated without changing the perimeter. This gives two distinct arrangements for the same pieces. The same argument applies to 𝛼+𝛾. Therefore, no member of Group 2 has a unique arrangement.

Since all sets of pieces fall in either Group 1 or Group 2, there is no set of pieces with a unique arrangement. Therefore, no 3x4 can be made.

QED.

## 3x5 Puzzle

#### Proof: Counterexample

A solution requires a set of pieces that can be assembled in exactly one way. There are 4 corner pieces, 8 side pieces, and 3 internal pieces. A 3x5 puzzle must use all 15 pieces. Any two distinct ways to assemble a 3x5 prove there is no unique solution.

The diagram below shows two distinct 3x5 arrangments using the set of all 15 pieces. This shows that there is no 3x5 solution.
QED

### Conclusion

The maximum solution is the 2x2 presented above.

The set of pieces is limited by excluding duplicates under rotation. In turn, this limits possible solutions to 8 different layouts. The 1-row layouts can be handled with exhaustive case-by-case analysis. The 2-row layouts are easily handled through a couple encompassing observations. The 3-row layouts can be addressed as 3x3, 3x4, and 3x5 cases: the 3x3 layout can be proved impossible by examining the cases allowed by the 6 perimeter permutations; the 3x4 layout can be proved impossible by examining the interior pieces; the 3x5 layout can be proved impossible by a counterexample. No larger layouts are possible, simply due to the limited set of pieces.

We start from preliminary observations.

Let the rectangle has size $$m\times n$$, $$m\le n$$. If $$m=1$$ then we can easily show that the rectangle contains at most three pieces, and in the latter case they are pieces $$sssb$$, $$sbst$$, and $$ssst$$. So we suppose that $$m\le 2$$

According to the puzzle conditions, each piece is unique and no piece has a nonidentity rotation transforming it to itself. Thus the following pieces are available.

Four corner pieces $$ssbb$$, $$ssbt$$, $$sstb$$, and $$sstt$$, eight side pieces $$sbbb$$, $$sbbt$$, $$sbtb$$, $$sbtt$$, $$stbb$$, $$stbt$$, $$sttb$$, and $$sttt$$, and three interior pieces $$bbbt$$, $$bbtt$$, and $$bttt$$.

Thus $$mn\15$$ and so $$m\le 3$$.

We call a piece symmetric, if a reflection transforms a piece to itself, or, equivalently, the list of the four sides of the piece in counterclockwise order is a list of the same piece. It is easy to check that the asymmetric pieces are exactly a pair $$\{ssbt,sstb\}$$ of corner pieces and two pairs $$\{sbbt,stbb\}$$ and $$\{sbtt,sttb\}$$ of side pieces.

Moreover, in each pair each piece is a reflection image of the other.

Now let us check all possibilities for a rectangle puzzle with a unique (up to a rotation) correct solution.

Clearly, all four corner pieces are used in the solution.

Note that a reflection of a solution has a different clockwise order of the corner pieces, so it can never be rotated to coincide with the solution.

Thus, since the solution is unique, it contains exactly one piece from some pair of asymmetric side pieces.

In particular, $$mn\le 14$$, so if $$m=3$$ then $$n\le 4$$.

Now let us go along the rectangle boundary and count the numbers of taps and blanks which we encounter.

The corner pieces provide four taps and four blanks, each symmetric side piece provides two taps or two blanks, and each asymmetric side piece provides one tap and one blank.

Since each of the total sums of taps and blanks equals the number of the boundary pieces which is $$2n +2m-4$$, so even,

we conclude that among the boundary pieces are exactly two asymmetric side pieces, one from each pair of asymmetric side pieces.

Moreover, since the number of blanks is equal to the number of taps, the number of symmetric side pieces providing two blanks is equal to the number of symmetric side pieces providing two taps.

Suppose first that $$m=3$$.

Suppose first that $$n=4$$. The above arguments imply that in this case the rectangle consists of four corner pieces, four symmetric side pieces, two interior pieces, and two asymmetric side pieces, one from each pair of asymmetric side pieces.

Then the numbers of taps and blanks between side and interior pieces are equal.

Then the numbers of taps and blanks at interior pieces are equal too.

This is possible only if the interior pieces are $$bbbt$$ and $$bttt$$.

Thus we determined all pieces of the solution but the asymmetric side pieces. Reflecting the solution, if needed, we can ensure that one of the asymmetric side pieces is $$sttb$$. There remains two possibilities for the remaining side piece, namely, $$sbbt$$ and $$stbb$$.

The following pictures show solutions instances for both cases.

But each of the solutions is not unique.

Indeed, in each of them we can rotate the third column and obtain a new solution.

Now suppose that $$n=3$$. The above arguments imply that the rectangle contains one symmetric side piece providing two blanks, one symmetric side piece providing two taps, and two asymmetric side pieces, one from each pair of asymmetric side pieces.

Reflecting the solution, if needed, we can ensure that one of them is $$sttb$$.

Then the other piece is $$sbbt$$ because otherwise it is $$stbb$$ and then it is easy to check that the corner pieces cannot be arranged properly.

By the same reason, the asymmetric side pieces cannot be at the opposite sides of the rectangle.

Thus the asymmetric side pieces are adjacent to a common corner piece, which, therefore, is symmetric.

Thus the $$L$$-shape constituted by five remaining boundary pieces consists of two symmetric side pieces, one symmetric corner piece, and two corner pieces $$ssbt$$ and $$sstb$$, symmetric to each other.

Then the interior piece is $$bbtt$$, because otherwise it is $$bbbt$$ or $$bttt$$, so the $$L$$-shape is symmetric and we can reflect it with respect to its symmetry line, providing a new puzzle solution.

The above implies that two symmetric side pieces are either $$sbbb$$ and $$sttt$$ or $$sbtb$$ and $$stbt$$.

But for any of two determined sets of the pieces we have at least two solutions, see the picture.

Finally we show that for any $$n\ge 3$$ there is no $$2\times n$$ rectangle puzzle with a unique correct solution.

Indeed, suppose for a contradiction that there is a required rectangle puzzle. Then its four corner cells should be filled by the pieces $$ssbb$$, $$ssbt$$, $$sstb$$, and $$sstt$$.

Rotating the rectangle, if necessary, we can provide that its leftmost column contains the piece $$sstt$$. Then the other piece it the leftmost column cannot be $$ssbb$$,

because otherwise the rightmost column cannot be filled with the remaining pieces $$ssbt$$ and $$sstb$$.

In any of the remaining cases both pieces from the leftmost column have taps at their right and both pieces from the rightmost column have blanks at their left.

But there are two ways to provide this configuration of the boundary columns:

$$\begin{matrix} sstt & \dots & sstb\\ ssbt & \dots & ssbb \end{matrix},$$ and $$\begin{matrix} sstb & \dots & ssbb\\ sstt & \dots & ssbt \end{matrix},$$ so the puzzle solution is not unique, a contradiction.