About 40 years ago, one of my cousins got a 9-piece puzzle that, according to family's legend, no one (in the family, at least) was able to solve. Then, two years ago, he brought it home, after finding it in an old drawer. Here is a photo of it:
After tinkering with the pieces for five minutes the honest way, during which the family's legend made total sense, I chose two alternative approaches:
1) To think outside the box and look for imperfections. The puzzle had camels, palm trees, palaces and pyramids, but their positioning and the cut of the pieces was not perfect. In less than 10 minutes, the solution was there. It was cheating, but I felt proud at the same time. Thinking outside the box has its own merit.
2) To explore all the combinations of the pieces, with a computer. For that, I needed to label the pieces from 1 to 9. Yes, from 1 to 9 and not from 0 to 8, because this post is all about nostalgia and I decided to program the code in good old Fortran, the language I learned at university. And Fortran indexes are from 1 to n. Also labelled the four sides of each piece, using this code:
1 = Camel
2 = Palace
3 = Palm Tree
4 = Pyramid
- = Left side
+ = Right side
+----------+ +----------+ +----------+
| +4 | | -2 | | -3 |
| | | | | |
|+3 P1 -3| |+1 P2 -4| |+1 P3 -4|
| | | | | |
| -1 | | +3 | | +2 |
+----------+ +----------+ +----------+
+----------+ +----------+ +----------+
| -3 | | -4 | | -1 |
| | | | | |
|+1 P4 -2| |-2 P5 +2| |-2 P6 +4|
| | | | | |
| +4 | | +1 | | +3 |
+----------+ +----------+ +----------+
+----------+ +----------+ +----------+
| -1 | | +1 | | -2 |
| | | | | |
|-3 P7 +2| |+3 P8 -2| |+4 P9 -3|
| | | | | |
| +4 | | -4 | | +1 |
+----------+ +----------+ +----------+
In raw-data form, we will feed the code the following numbers, where each row is a piece, and where the columns are the sides of each piece:
-1 -3 4 3
3 -4 -2 1
2 -4 -3 1
4 -2 -3 1
1 2 -4 -2
3 4 -1 -2
4 2 -1 -3
-4 -2 1 3
1 -3 -2 4
The code can be found here, and the input table here. It uses Heap's algorithm to generate all possible permutations. The code just tries each permutation and adds the numbers of touching sides. A permutation is a solution when the total sum is 0. Compile and run the Fortran code with:
$ gfortran camel.f -o camel
$ ./camel
Since pieces 2 and 8 are identical, we expect twice as many solutions (the code deals with the 9 pieces as if they were all different). And since a puzzle can be rotated 90, 180 and 270 degrees, we expect to find each unique solution appearing four times, one per global orientation. So, for each unique solution, we expect 8 lines from the output of the program. We run it (it only takes 0.127 s) and get the following:
5 4 8 2 4 3 1 2 7 4 6 4 2 3 3 3 9 3
5 4 2 3 4 3 1 2 7 4 6 4 8 2 3 3 9 3
9 1 3 1 2 1 6 2 7 2 1 4 4 1 8 4 5 2
8 4 3 1 1 4 4 2 6 3 9 2 2 2 7 3 5 3
2 1 3 1 1 4 4 2 6 3 9 2 8 1 7 3 5 3
9 1 3 1 8 4 6 2 7 2 1 4 4 1 2 1 5 2
8 3 1 3 5 1 3 4 7 1 2 4 9 4 6 1 4 4
2 4 1 3 5 1 3 4 7 1 8 3 9 4 6 1 4 4
1 3 9 1 5 2 3 4 6 2 7 2 8 3 4 1 2 1
4 2 6 3 9 2 8 1 7 3 3 2 5 3 1 1 2 2
5 1 7 1 8 3 9 4 6 1 4 4 1 2 3 3 2 3
5 1 7 1 2 4 9 4 6 1 4 4 1 2 3 3 8 2
1 3 9 1 5 2 3 4 6 2 7 2 2 4 4 1 8 4
4 2 6 3 9 2 2 2 7 3 3 2 5 3 1 1 8 1
8 2 4 3 2 2 7 4 6 4 3 2 5 4 9 3 1 1
2 3 4 3 8 1 7 4 6 4 3 2 5 4 9 3 1 1
16 lines! This means there are two unique solutions! Each line has 18 columns. The meaning of the numbers is the following. The 18 numbers are just 9 pairs of numbers, giving us (number of the piece [1-9], orientation [1-4]). We need to place the pieces from left to right and from top to bottom. The orientation labels mean: rotate -90º (i.e. clockwise) times the label. Here we show the solution corresponding to the first line:
The 2nd line is the same as the first but swapping the pieces 2 and 8. The 3rd line is just the same as the first but rotated 180º. But the 4th line gives us the other, unexpected solution:
How cool is finding two solutions after 40 years thinking we didn't find the solution? The difficulty was well justified: how many combinations does this puzzle offer? Assume first the 9 pieces are different and that their local orientations do not matter. Then we have 9! = 362880 permutations. Since two pieces are identical, we have 9!/2 = 181440 permutations. Now consider that each piece has 4 orientations. This means we need to multiply by 4^9 = 262144. This gives a total of 47563407360 cases. But we divide by 4 to get rid of the global orientation multiplicity, so we get 11890851840, which is basically 10^{10}. An astonishing number. At one case a second (optimistic), we would take 376.8 years to cover all the possibilities.
There must be a logical way to get to a solution, but after some minutes of trying, I could not find any. If you find one, please make a fool out of me and send it so I can, with proper credits, share it here.
Comments? Just send a message and it will be copied here (please specify your privacy choices).