Proving a jigsaw is possible

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?

• "if we run through every possible connection type for each piece" - I'm not sure I understand what you mean. What about the piece with all straight sides, the one with all concave sides, and the one with all convex sides? Could you clarify your statement? – Michael Lee Jun 11 '17 at 19:31
• What you're describing sounds like a brute-force method of generating a solution if one exists, but definitely not a proof of existence. – Michael Lee Jun 11 '17 at 19:34
• If there is such a solution, you'll find it. If there isn't, you won't. I see no reason to rule out either possibility. – Robert Israel Jun 11 '17 at 19:49
• It won't if there isn't a solution. – Robert Israel Jun 11 '17 at 20:11
• @Jens; Robert Israel is saying that while the approach you're suggesting is a valid strategy to find out if there is a solution or not, it is not in itself a proof either way. You could end up trying every single combination and find that none of them actually make a valid grid (though in this particular case, as Bram28 answered, it is in fact possible and therefore brute-force will indeed find a solution when applied). As a silly example of the negative, I could claim a boolean "a" exists such that "a = not a", with the "proof" that if I try every possible value of a, one of them must work. – Dave Jun 11 '17 at 22:29

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 !)

• I'm convinced. Thank you. – Jens Jun 11 '17 at 21:13
• @Jens You're welcome! :) I was playing with those 1,2,3's for a while, and initally had a hard time (which is why it wasn't at all clear to me there had to be a solution) ... But then I found the right way to think about it, and just had to find a sequence with all possible pairings – Bram28 Jun 11 '17 at 21:16
• By the way, this is a de Bruijn sequence of order 2 on an alphabet of size 3. – Rahul Jun 11 '17 at 23:01
• @Bram28 Here's an illustration of your solution, if you want to add it to your answer: imgur.com/a/H78uk – Frxstrem Jun 12 '17 at 0:23
• Is this answer unique (up to reflections/rotations) or are there several options for coding each axis? – Neil_UK Jun 12 '17 at 8:33

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 there (without duplicates).

Associate now colors to each side according to its aspect :

• R$$\to$$"flat side",
• G$$\to$$"convex side",
• B$$\to$$"concave side". This gives figure 2.

Remarks:

1) The color sequencing of lines and the color sequencing of columns have been deliberately chosen different. In fact there are 24 different color sequencements. Why that ? Identify the East and West side ; similarly, identify the North and South sides. In other words, 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$$. We fall thus into 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 showing 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