My mother gave the fam a new game for Xmas called “The Impossible Puzzle.” Or maybe that was the company name. Either way, the label is certainly apt.
The puzzle is composed of nine, 4-sided pieces with interlocking parts in the shapes of the 4 card suits (hearts, diamonds, etc). There is only one way to lock the 9 pieces into a 3X3 square, and the game touts the fact that “there are over 300,000 combinations, only one of which is correct.”
My mother, her bf, and myself all fiddled with this puzzle for a while before becoming too frustrated. There seemed to be no way to logically sort through the options of all possible arrangements and rotations of the pieces and clearly a brute-force method of trying all combinations would take way too long by hand. But maybe not for a computer. So, I figured this would be an excellent opportunity to try out my programming skills.
The idea seemed simple enough: I needed a way to model each puzzle piece in a program, and then have the program arrange those 9 pieces in each of every possible way and then test whether or not that arrangement was a solution. To test for matches, I decided that I would assign each shape a number, and the positive version would represent the “outy” and the negative would be the “inny”. The test for a matching pair would then be “if(side A = the opposite of side B), then they are a match”. For illustration, see the diamond shape in the figure above.
I then needed three more things:
- A way to re-arrange the puzzle pieces methodically into every possible 3×3 spacial arrangement;
- A way to rotate each piece methodically for every possible arrangement of rotations, within each spacial arrangement;
- A test for whether or not the arrangement was a solution.
I’ll go through these one-by-one, then hit the programming in a later post.
1. Spacial Re-arrangement
Since there are exactly 9 different pieces, finding the number of possible spacial arrangements requires the use of permutations.
Starting with all nine pieces, I have 9 options for the first position, p. Since I now only have 8 puzzle pieces left, I only have 8 options for p. Then 7 for p and so on. That means that the number of possible arrangements of these nine puzzle pieces is equal to
9*8*7*6*5*4*3*2*1 = 9! =362,880
So, the game’s claim of “over 300,000” was correct, but is an incredibly low-ball estimate because it is already too low before taking into account that the pieces have 4 different rotational positions as well!
Now, I have a suspicion that there are actually fewer than 9! arrangements, since the puzzle is a 2D structure. For example, the arrangements
| 1 2 3 | | 9 8 7 |
| 4 5 6 | and | 6 5 4 |
| 7 8 9 | | 3 2 1 |
Are actually just the same arrangement where the entire puzzle is rotated 180°. In fact, rotating the puzzle by 90° increments will give you the same puzzle (this makes perfect intuitive sense; just imagine turning a jigsaw puzzle), but this is only true if the puzzle pieces are also rotated (a little less intuitive). The end result is that we could decrease the total number of computations required by a factor of 4.
So, we have 9! ways of arranging this puzzle into a 3×3 grid, but we also have to bear in mind that each puzzle piece has four possible rotations. For example, in Figure 1, the pieces are in a rotation in which the “inny” and “outy” diamonds can connect. If we were to rotate the “inny” piece by 90°, the two pieces can no longer be connected.
How many different ways can we rotate the 9 puzzle pieces? Since the rotation of one has no bearing on the rotation of another, the situation is different than before. At position p we have 4 options. At p through p we also have 4 options. The total number of rotational arrangements is then
(4*4*4*4*4*4*4*4*4 )= 49 = 262,144
which is a similarly huge number. It gets a lot more frightening when you realize that this is how many rotational arrangements there are for each positional arrangement! Our total number of potential solutions is then, taking into account piece rotation, puzzle rotation, and piece arrangement:
(possible arrangments)*(possible rotations per arrangement) =
(362,880/4)*262,144 = 23,781,703,680
Yeah. 23 billion.
Where the hell did they get 300,000? They were off by a factor of 100,000! Or perhaps I’m just doing something wrong; that whole combination vs. permutation thing has aways confused me :).
3. Testing Potential Solutions
We now have an idea of how many different solutions there are to this problem, but only one of them (the game-makers claim) is correct! So we also need a way to test for correctness.
The most straight-forward thing to do would be to check whether or not each neighboring side is a match (i.e. is equal but opposite in value). There are 12 pairings that have to match in the correct arrangement.
If each puzzle piece has a defined top, bottom, left, and right, then we simply need 12 comparison tests in the spirit of “if the right side of the top-left square is equal but opposite to the left side of the top-middle square, they are a match.”
Now that I have laid out the problem and a rough idea of what needs to be accomplished to solve it, we can walk through a short computer program that will do this work for us. I’ve already finished the program and successfully tested it against fake data that I knew had a solution, so I will run it overnight tonight against the real puzzle and hope that my Eee PC’s tiny processor can chug through all the necessary calculations fast enough to have an answer for me by morning. Once it works, I’ll write up a post on the program itself.
That first test against the real puzzle didn’t work, because I had recorded the pieces incorrectly. That was fixed and the solution was found, and this is described in a later post.