8 and 15 Puzzles | Algorithms and Data Structures (2024)

The (N² − 1)-puzzle is a collection of N²−1 movable tiles number 1 through N²−1together with one blank arranged in an N×N square. Figure 1 shows aneight-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 ofthe blank. An example of such a move is to move tile 6 into the blank as is shown in Figure 2. Given anyarrangement 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 makinga sequence of valid moves, to transform the puzzle into the original shown inFigure 1. Figure 3 shows a permutation with a single move which places 6 intothe correct location. Given a permutation, a solution is a sequence of moves whichtransforms 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 blankhave solutions.

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

The data structure used to efficiently solve the A* algorithm is a modified heapwhich 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 andtherefore the run time would be slowed significantly.

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

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

Figure 4. An updatable priority queue.

For example, Black hashes to 4 and has the highest priority, thereforeit 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. Beingstored 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 stateof 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 theManhattan 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 isgiven by the formula2/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 usingthe complete binary tree representation and a chained hash table. The nodes in thehash table are reasonably independent of the problem being solved, requiring onlythat the class have a member function with the signature int lower_bound() constwhich can be called to calculate the lower bound on the distance from the objectto the solution.

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

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

Figure 7. A permutation of the eight-puzzle.

Dijkstra's algorithm found the minimum solution of 24 moves after havingconsidered 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 distanceis only really useful in the last stages of finding the solution. The maximumheap size was still 22899.

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

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

Figure 8. A permutation of the fifteen-puzzle.