 |
| Completed Puzzle |
Dennis gave me this puzzle for my birthday. I spent a few minutes trying to solve it but then realized I could write a computer program to solve it, much like I did for another puzzle he gave me.
It didn't take long to write it, but it took a while to track down the bugs and to polish it up a bit.
 |
| Puzzle Pieces |
The first problem was how to represent the puzzle pieces in the program. With the cube puzzle, I was able to use a 64-bit integer to represent the 4 x 4 x 4 cube. This puzzle was a little trickier.
The digits here are modeled on the seven segment displays that are common in simple electronic devices. Note that each segment is shaped like a rectangle with a triangular point on each end. If the puzzle pieces closely followed the electronic pattern it would have been simple to encode them as data. However, some of the pieces, like the zero, one and seven, included a bit that isn't part of the original pattern, and some (the zero) were missing a bit.
 |
| Zero |
I decided to 'draw' the digits using ASCII characters. Each true segment was represented by three characters. I couldn't come up with a good visual method of representing multiple triangles in one space, so I gave each segment three full spaces and left a space between segments.
 |
| Playing Field |
The playing field, like the individual digits, is an array of character strings. Valid places are marked by vertical bars or hyphens. Invalid places are marked with X's and spaces.
Most of the mechanics of the program were pretty straight forward and didn't give me any trouble, but I tried to use a minimal amount of space for the puzzle pieces and that kept biting me. Eventually I realized I needed an extra row of spaces surrounding each character and around the playing field as well and then things started coming together. (It's not that I was trying to save space, 200 bytes isn't going to make any difference in a machine with gigabytes of RAM. I was trying to adhere to the old dictum of 'necessary and sufficient'.)
I let it run for a while and it found multiple solutions, but after a 20 odd hours I said this is enough, shut it down and started looked at just how many combinations I was testing. Pieces can be rotated through four different orientations and can be flipped to make a mirror image. Not all pieces need all four rotations. Turn some pieces (like the two) 180 degrees, and you are back where you started. And for some, the mirror image is identical to the original. So I modified the program to use this information. Now it runs to completion in just over an hour and found 16 possible solutions.
Every solution required at least one piece to be flipped to become its mirror image.
Digit: 0 1 2 3 4 5 6 7 8 9
Solution 1: 0 0 0 0 0 0 0 1 0 0
Solution 2: 0 0 0 0 0 0 0 1 0 0
Solution 3: 0 0 1 0 0 1 0 1 0 0
Solution 4: 0 0 1 0 0 1 0 1 0 0
Solution 5: 1 0 1 0 0 0 0 0 0 0
Solution 6: 1 0 1 0 0 0 0 0 0 0
Solution 7: 1 0 1 0 0 0 0 0 0 0
Solution 8: 1 0 1 0 0 0 0 0 0 0
Solution 9: 1 0 1 0 0 0 0 0 0 0
Solution 10: 1 0 1 0 0 0 0 0 0 0
Solution 11: 1 0 1 0 0 0 0 0 0 0
Solution 12: 1 0 1 0 0 0 0 0 0 0
Solution 13: 1 0 0 0 1 0 1 0 0 1
Solution 14: 1 0 0 0 1 0 1 0 0 1
Solution 15: 1 0 1 0 1 1 1 0 0 1
Solution 16: 1 0 1 0 1 1 1 0 0 1
Table showing which digits were flipped
For pieces in a vertical orientation, there are 15 possible positions on the playing field. Pieces lying on their sides have 16 possible positions. Zero is a special case as it is the first piece we play. Any position past the halfway mark can be considered a mirror image of the playing field and so we only have 10 possible positions for the zero (6 in vertical orientation and 4 in horizontal).
This gives a total of 4.3 times 10 to the 18th power possible placements. The program tried approximately 450 million combinations on its way to finding the 16 solutions.
No comments:
Post a Comment