Proving a jigsaw is possible

Question

This is an offshoot of this question.

Suppose we have jigsaw puzzle pieces which are basically squares but where each side can be either straight, concave or convex. An example of three such pieces is shown below:

It is clear that there can be $3^4=81$ different types of pieces. I was wondering, given one of each type (and with no rotations or flips allowed), whether it was possible to create a standard jigsaw puzzle, using just those $81$ pieces. By "standard jigsaw puzzle" I mean one of dimensions $m \times n$ where all perimeter sides are straight.

A $1\times 81$ puzzle is clearly not possible as it would require all $81$ pieces to be straight on both the left and the right side. A similar argument holds for a $81\times 1$ puzzle.

A $3\times 27$ puzzle would require $27$ pieces with a left straight side and $27$ pieces with a right straight edge, and while it is true that such two sets exist, they have an overlap of $9$ pieces. This is therefore not possible. As before, a similar argument holds for a $27\times 3$ puzzle.

This leaves the $9\times 9$ possibility. A priori, I can see no reason this shouldn't be possible. And I think I have a proof that it is possible, which is what I would like your opinion on.

Given a $9\times 9$ puzzle, we have the situation below:

Each black side of a piece is fixed, but each green side of a piece represents a possible connection type. A connection type could be a "straight - straight", "concave - convex" or "convex - concave" type. It seems to me that if we run through every possible connection type for each piece, one of those scenarios must give a puzzle where each of the $81$ piece types is used exactly once.

Am I right?

Answer 1

I wouldn't call what you say a proof ... It is not immediately clear from what you say that you will indeed get all possible pieces in there.

However, your hunch is correct: this puzzle is indeed solvable. Here is a proof:

Let's call the straight edge $1$, the concave edge $2$, and the convex edge $3$. Now, label the $10$ vertical edges in each row of your $9 \times 9$ board with $1,1,2,3,1,3,3,2,2,1$ in that order. Note that if you look at two sucessive edges (so these would be the left and right edges of a piece), you get all possible pairings: $11,12,23,31,13,33,32,22,21$. Hence, pieces in the same column will have the same left and right edge, but pieces in different columns will have differen left/right pairings.

Ok, do the same with the horizontal edges from top to bottom. This will give you all possible pairings for top and bottom edges. So, since different rows have different top/bottom pairings, and since different columns will have different left/right pairings, you do indeed get all $81$ possible combinations, and thus all the $81$ different pieces in there.

Here is the resulting solved puzzle (thanks @Frxstrem !)

Answer 2

This answer, complementing the excellent answer of @Bram28, explains the idea with line coloring. It is possible (see figure 1) to place 10 horizontal and 10 vertical lines using (R,G,B) colors in such a way that the $3^4=81$ different squares are present (for example, there is a unique square with North, West, South, East colored (G,B,R,R) resp.: this square is found in the South East corner). Check that the $3^4=81$ different squares are present once and only once.

Now, attribute colors to each side according to its shape:

• R$\to$"flat side",
• G$\to$"convex side",
• B$\to$"concave side".

This gives figure 2.

Remarks:

1) The color sequencing of lines and columns has been chosen different in a deliberate way. In fact there are 24 different color sequencements. Why that ? Identify East and West side of the board ; similarly, identify the North and South sides ; said otherwise, consider our puzzle as drawn on a torus, so $9 \times 9$ is the number of pieces and as well the number of lines. This number $9$ is, I would say by chance, a power $9=3^2$, allowing to use the framework of de Bruijn sequences here of type $B(3,2)$. Such a sequence is made of $3^2$ "letters" (imagined arranged in a ring) such that, by sliding a window of width 2 on the sequence, one gets all the words on an alphabet of 3 items : R,G,B. An example : RRGGBBRBG where the window sliding will provide RR,RG,GG,GB,BB,BR,RB,BG and GR, all the words with 2 letters on an alphabet of 3 (please note that the last word, GR, has been obtained by wrapping the sequence). For more, see (https://en.wikipedia.org/wiki/De_Bruijn_sequence) where you will find a formula explaining that there are $6^3/3^2=24$ of them.

2) Out of a solution, one can generally build a big amount of other solutions. For example, in the case of the given figure, consider the two identical $1 \times 4$ (or $1 \times 5$, or $3 \times 3$... !) rectangles in the South West and North East corners of the puzzle : another solution is provided by switching them.

---

Edit : (Feb 8 '18)

Related :

http://erikdemaine.org/papers/Jigsaw_GC/paper.pdf

What is known about this jigsaw combinatorics problem?

Somewhat related :

https://puzzling.stackexchange.com/a/48864

I found an old reference mentionning an analogous type of pieces in an old-fashioned delicious booklet entitled "New Mathematical Pastimes" by Major McMahon, Cambridge, 1921 (https://archive.org/details/newmathematicalp00macmuoft) (page 69) .