15 Puzzle solver

This program depicts a method for solving the 15 puzzle.

I wrote this to see if the explicit method I was using to solve this puzzle could be encoded, and whether there were puzzle instances my method would not work on.

A ran a separate testbed app that did thousands of runs to determine the success rate of various methods for solving this puzzle. For each run, a random instance of the puzzle was produced by making over 100 random moves. In this way, it is clear that the instance of the puzzle would be solvable.

An earlier method I used worked ~80% of the time for 100,000 runs. The method I present here was successful for all 100,000 runs, and then millions of runs after that.

When you step through the algorithm, you'll be able to clearly see the method for solving the puzzle.

Description of the method:

1) Move 1 into position
2) Move 2 into position
3) Get 4 out of the way
4) Move 3 to the top right
5) Move 4 below the 3
6) Slot in 3 and 4 in consecutive moves

Top row is done. Top row tiles are never touched again.

7) Move 5 into position (never touching the top row)
8) Move 6 into position
9) Move 8 out of the way
10) Move 7 to the top right
11) Move 8 below the 7
12) Slot 7 and 8 in consecutive moves

Top 2 rows are done. Top 2 rows are never touched again.

13) Move 10 out the way
14) Move 9 into position
15) Move 10 next to the 9
16) Slide 9 and 10 in consecutive moves so they are out of the way
17) Move 11 next to 10
18) Move 12 next to 11
19) Move 9,10,11,12 in 4 consecutive moves so that they are in a solid block to the left
20) Rotate the remaining tiles (13,14,15) until the 13 touches the 12
21) Rotate all 8 tiles until they are all in position

And now the puzzle should be solved.

Here are the controls:

'c' runs the algorithm continuously until the puzzle is solved
'p' pauses the continuous run
's' Moves one tile (steps the algorithm until it moves a tile)
'r' Generates a new puzzle
'q' or Esc closes the program

Notes on the implementation:

This program is another demonstration of the value of moving an algorithm into an updatable object that can be queried. By this I mean that instead of implementing your algorithm in a function, you implement it as a state machine, with the various states corresponding to different stages of the algorithm. Local variables of the function become member variables of this object, and any recursive function calls are handled by using a stack. In this way, it is possible to observe the operation of the algorithm, and perhaps do other things in the meantime.

From the caller, its the difference between doing this:

RunAlgorithm(data);

and this:

Algorithm a;
a.Reset(data);
while(!a.Finished())
{
a.Update();
}

You can see where the second approach would have many advantages.

Screenshots: