As an interesting exercise for myself, I recently coded a tesserae/tile program to solve a 3x3 puzzle using a brute-force approach; the puzzle has (9!)*(4^9) or ~95 billion possible states if you ignore symmetry.
Source code (in C#) is provided below:
The initial game (tile 0-2 in first row, tile 3-5 in second row, 6-8 in third row):
and the solved game:
Solution output was (tile # and how many times to rotate clockwise):
| 1 rotate 2 | 7 rotate 1 | 4 rotate 1 |
| 3 rotate 3 | 8 rotate 3 | 0 rotate 1 |
| 6 rotate 3 | 2 rotate 3 | 5 rotate 3 |
It took ~11 hours of computation time on a P4 Dell d810 laptop and examined ~18.5 billion board states at a rate of ~450k states examined per second. Perhaps there is a better way of solving this quickly, but not solvable quickly in general as I believe this is a specific instance (3x3) of the NP complete generalized tiling problem introduced to me as a first-semester Freshman at Georgia Tech by Russ Shackelford. Funny how everything comes back around later in life.
Special thanks to the company b. dazzle, inc. who made the puzzle.
Later in 2008 I bought and solved another with the program (this one is of planets):
This page was last updated on 8/15/2008.