8-Puzzle Solver

The 8-Puzzle Solver is a classic AI program that uses the A* heuristic.

  • A* maintains two lists, called open and closed.
  • At the beginning of the algorithm, the initial node is placed on the open list. The list is sorted according to a fitness function that measures how close the state of the node is to the goal state. Thus, we are really dealing with priority queues.
  • At each step, bestNode is removed from the open list. In this case, bestNode is always the head of the open list. If the state of bestNode is the goal state, then the algorithm terminates. Otherwise bestNode is expanded (we determine all the possible states that can be reached within a single move), and bestNode is placed on the closed list.
  • Ideally the successors of bestNode should be placed on the open list if either:
    • the successor is not already on the open or closed list, or
    • the successor is already on the open or closed list but has a lower cost.


8-Puzzle
Screenshot of 8-Puzzle Solver.

Implementation

My program is now about as sophisticated as I want to make it. First of all, I included a check to see if the puzzle configuration is valid before attempting to run a search algorithm. This is done as follows:

  • Move the space to the bottom right corner.
  • From there, count the number of swaps needed to put the puzzle in order.
  • As long as the puzzle is square, if the puzzle has an odd number of rows, there must be an even number of swaps. If the row count is even, there must be an odd number of swaps. If not, the puzzle configuration is unsolvable.

Next, I upgraded the open list to a Fibonacci heap and the closed list to an AVL tree. For a Fibonacci heap, insertions take constant time and extracting the minimum takes O(lg n) time. The priority queue, on the other hand, takes O(n) for inserts but constant time to remove the minimum cost node. The Fibonacci heap alone was an improvement, but it was not a drastic change. The AVL tree was crucial for making a faster A* algorithm. Insertions and searches require only O(lg n) time on the height-balanced tree, while taking O(n) on the priority queue. Thus, it is easy to see that the AVL tree was a real performance booster, and the combination of these two data structures led to astounding results. Using the MS JVM with Internet Explorer 5.5 on an AMD Athlon 800, one configuration that takes 5.8 seconds with A* takes about 0.17 seconds with enhanced A*. However, there are still some 15-puzzle configurations that the program cannot solve because they require close to 50 moves.


I included breadth-first search in the list of heuristics just for educational purposes. It performs very poorly in comparison with the A* family of algorithms, only solving configurations that take up to 10 moves.

This program is fairly easy to use. The only thing that may be confusing is entering the initial state of the board. To do this, just list the numbers of the pieces you want in order from left to right starting at the top row and 0 for the space. For example, 2 4 0 1 8 5 3 6 7 is what you would enter for the board configuration that takes 0.17 seconds on my computer with enhanced A*, like the following:


2 4 0
1 8 5
3 6 7