Sliding Number Puzzle
NOTE: Scrambling more moves can lead to very long computations,
if the program runs for too long it stops (so your computer doesn't
This solution uses a Java Applet (you need the Java plugin) to solve this puzzle.
The rules are such:
- One block can move at a time and only to an empty, adjacent space.
- The goal is to get Top row: 1, 2, 3; Middle row: 4, 5, 6; Bottom row: 7, 8
This is solved here using the A* Search algorithm with
the Manhatten distance of misplaced tiles as the heuristic.
Origionally a tree search was used (each state could be revisited),
but fewer solution depths could be found. With the graph search,
once a state has been visited, it will not be visited again.
The maximum depth (number of moves) to reach a solution is 31,
but even with the graph algorithm, only solutions of depth 16
or so can be found in a couple seconds.