Sliding Number Puzzle

A.K.A. 8-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 lock up).

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.