The (N² − 1)-puzzle is a collection of N² − 1 movable tiles number 1 through N² − 1 together with one blank arranged in an N × N square. Figure 1 shows an eight-puzzle.

Figure 1. An eight-puzzle.

The only valid moves are to move a tile which is immediately adjacent to the blank into the location of the blank. An example of such a move is to move tile 6 into the blank as is shown in Figure 2. Given any arrangement of the tiles, there are between two and four valid moves.

Figure 2. A valid move of the eight-puzzle.

The objective is to take a permutation of the tiles and the blank; and, by making a sequence of valid moves, to transform the puzzle into the original shown in Figure 1. Figure 3 shows a permutation with a single move which places 6 into the correct location. Given a permutation, a solution is a sequence of moves which transforms the permutation into the solution.

Figure 3. A move in a permutation of the eight-puzzle.

Please note, only half of all permutations of the tiles and the blank have solutions.

The algorithm presented uses an A* search to find the solution to the (N² − 1)-puzzle: arranging the numbers in order with a blank in the last location.

The data structure used to efficiently solve the A* algorithm is a modified heap which is able to allow the user to update the priority in O(ln(n)) time: a index to each entry is stored in a hash table and when the priority is updated, the index allows the heap to, if necessary, percolate the object up.

Without the hash table, objects in the heap could not be easily accessed and therefore the run time would be slowed significantly.

The design, shown in Figure 4, is as follows:

• Each object is placed into the hash table corresponding to its bin, here shown using a chained hash table.
• The nodes within the chains store not only the object, but also an index into the heap.
• The heap only stores pointers back to the nodes in the hash table.

Figure 4. An updatable priority queue.

For example, Black hashes to 4 and has the highest priority, therefore it is in the 1st location of the heap and the index 1 is stored in the node. Similarly, Orange hashes to 7 and has priority lower than Brown. Being stored in index location 4, the node in the hash table stores 4.

There are three distances which can be used to measure the distance between the state of a puzzle and the solution:

• The discrete distance (0 if equal and 1 otherwise),
• The Hamming distance (the number of tiles out of place), and
• The Manhattan distance (the sum of the minimum number of steps to move each tile (assuming no other tiles) in its correct location),

For example, Figure 5 shows the solution to the eight-puzzle and a permutation of the tiles.

Figure 5. The solution to the eight-puzzle and a permutation of the tiles.

The discrete distances between the permutation and the solution is 1 (they are different). Using the Hamming distance, the distance is 8—only one tile is in the correct location. This is shown on the left of Figure 6. Using the Manhattan distance, the distance is the sum of the moves shown in Figure 6: 2 + 0 + 4 + 2 + 1 + 1 + 2 + 3 + 1 = 16.

Figure 6. The Hamming and Manhattan distances of the permutation from Figure 5.

The formula for the average Manhattan distance of a random permutation is given by the formula 2/3(N − 1)(N² + N − 3/2), which, for this case is 14.

The Updatable_heap data structure makes use of a heap as an array using the complete binary tree representation and a chained hash table. The nodes in the hash table are reasonably independent of the problem being solved, requiring only that the class have a member function with the signature int lower_bound() const which can be called to calculate the lower bound on the distance from the object to the solution.

The class also tracks the size and the maximum size of the heap (the maximum number of objects in the priority queue).

To demonstrate the algorithm and the solution, Figure 7 shows one puzzle for which the solution was found using the discrete, Hamming, and Manhattan distances to guide the A* search.

Figure 7. A permutation of the eight-puzzle.

Dijkstra's algorithm found the minimum solution of 24 moves after having considered 139466 possible solutions (visited 139466 vertices) during the search and the maximum size of the heap was 24154.

Using the Hamming distance, the number of puzzles considered dropped to 127643. This small reduction is almost certainly due to the fact that the Hamming distance is only really useful in the last stages of finding the solution. The maximum heap size was still 22899.

Using the Manhattan distance, only 2751 vertices were visited and the maximum heap size was 1501.

Solving fifteen-puzzles is much more difficult: the puzzle in Figure 8 has a solution of 50 moves and required that 84702 vertices (different permutations of the puzzle) be visited and the maximum heap size was 72340.

Figure 8. A permutation of the fifteen-puzzle.