The (*N*^{2} − 1)-puzzle is a collection of *N*^{2} − 1
movable tiles number 1 through *N*^{2} − 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*^{2} − 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*^{2} + *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.