## 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.

### Variations