Proving a jigsaw is possible

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

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