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?
Best Answer
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 !)