Walking Distance

Translation

This translation is far from authentic. I will be grateful to anyone who can help in translation from Japanese.

ID (Inverse Distance) and WD (Walking Distance) are invented by Ken'ichiro Takahashi (takaken). Original description is available by this link.

02 / 12 / 2012

How to write 15 puzzle solver

To solve relatively simple puzzles, breadth-first search can be used. As far as it known, 4 × 3 (11 puzzle) is hardest solved puzzle. Using breadth-first search to solve 4 × 4 (15 puzzle) is not possible.

In this case, iterative deepening may be used. In this algorithm, parts of the search are executed repeatedly, resulting in slowdown.

Next, some optimizations of the iterative deepening will be discussed.

Iterative deepening

With iterative deepening, at each step of the search there is a limit on depth. Search repeats many times with increasing limit on depth until solution will be found.

This algorithm has advantages. First, it always finds optimal solution. There is no need to store many states in memory. Also, implementation of the algorithm is simple.

However, there are some drawbacks. Besides the fact that parts of the search are repeat many times, there is a problem that search spends many time in loops. Partially this problem can be resolved by memorizing last made move and disabling move that undoes this move. Even such simple optimization is able to significantly reduce running time.

Lower bound. Manhattan distance

In iterative deepening, heuristic search can be used.

In the example below, the number of moves required to solve the puzzle is at least 10. Indeed, tile 1 cannot be solved in less than 2 moves, tile 2 - in 2 moves, tile 3 - in 3 moves, tile 4 - in 1 move, and tile 5 - in two moves. Thus lower bound on the number of moves in optimal solution is

2 + 2 + 3 + 1 + 2 = 10 moves.

51
342

Such lower bound is used in the following inequality:

depth + LowerBound > limit

If this inequality is true, current branch is a deadlock.

Heuristic described above is mentioned in bibliography as Manhattan Distance (MD).

Increasing depth limit by +2

The number of moves in solution is even or odd, depending on the location of empty square. Let's color board with black-white checkered pattern. Now, after each move the color visible in empty square changes from black to white and vice versa.

If after some sequence of moves this color is the same as was before, then the number of moves in this sequence is even; if the color changes, the number of moves is odd.

Thus, after initial depth limit was set to 0 or 1, after each search step it is admissible to increase limit by +2, not by +1. Moreover, depth limit can be initialized with heuristic value such as Manhattan Distance.

ID (Invert Distance)

Invert Distance is other admissible heuristic. It uses concept of the number of inversions. Inversion arises when tile with greater number locates after tile with lesser number, "reading" tiles left-to-right, top-to-bottom.

Note that horizontal moves do not change the number of inversions. Vertical move changes the number of inversions by -3, -1, +1 or +3.

Therefore, minimum number of vertical moves in the solution can be calculated as invcount / 3 where invcount is the number of inversions. Moreover, when remainder arises, it can be added too:

vertical = invcount / 3 + invcount % 3

The same procedure is applied second time to calculate minimum number of horizontal moves. This time, tiles must be read top-to-bottom, then left-to-right.

Invert Distance is the sum of two calculated values:

ID = vertical + horizontal

For example, in the following configuration optimal solution is 78 moves, MD = 58, ID = 70.

15 14 13
12 11 10 9
8 7 6 5
4 3 2 1

Heuristic value is maximum of MD and ID. In such bundle, different heuristics compensate drawbacks of each another.

WD (Walking Distance)

Invert Distance splits lower bound into vertical and horizontal components. Manhattan Distance can be divided too.

In the example below, MD = 3 which does not mean that the solution is actually three moves!

1 2 3
5 6 7 8
9 10 11 12
13 14 15 4
MD = 3
optimal solution 19

Why not try to improve heuristic? Key idea is the same: vertical and horizontal moves are counted separately.

Consider vertical moves, ignoring any horizontal. Each configuration can be written in table form. Configuration from the example above looks like this:

From 1 row From 2 row From 3 row From 4 row Empty square
1 row 3 0 0 0 ← Here
2 row 0 4 0 0
3 row 0 0 4 0
4 row 1 0 0 3

When row containing empty square is known, it is possible to move to this row from row just above or just below. In the given example, one of 4 tiles from 2nd row that are in 2nd row, can be moved to 1st row. Empty square will move to the second row.

Using such "moves", it is possible to run breadth-first search backwards from the goal state. All values are saved in database. The number of distinct tables is 24964.

The same database is used when calculating the number of horizontal moves.

In the configuration above, MD = 3, while WD gives 11 moves.

One additional advantage of the Walking Distance is that WD is never less than MD. In other words, WD is more informative heuristic. So MD becomes absolutely unnecessary.

Maximum WD value is 70.

WD transition table

Heuristics MD and ID can be passed as parameters in search function, so there is no need to recompute these values each time. WD cannot be computed in such simple way; to compute WD value, one must find in the database key.

However, there is a good way to calculate WD quickly. For every table and for each possible move, special database stores link giving result of applying the move to the table.

Source code and results

Implementation of the iterative deepening with ID and WD.

  1. puz15wd.c - a program to make WD database
  2. puz15sv.c - main program to solve 15 puzzle

Main program is [puz15sv.c]. To compile and run, you must keep in the same folder database puz15wd.db obtained by running first puz15wd.c.

The program is too slow to be used in determining maximum number of moves in optimal solution. However, as a standard solver, it is effective enough.

There is also Windows version.

Conclusion

The program may face hard configurations such as "configuration of the devil" shown below. WD and ID are too low. This problem can be solved by using PDB (Pattern Databases) [1].

1 5 9 13
2 6 10 14
3 7 11 15
4 8 12

(WD = 20/20, ID = 12/12) LowerBound = 40
[72 moves] time=77565sec (about 21 h 33 m)
15 14 13 9 10 13 14 11 13 14
11 15 12 13 7 8 13 7 14 6
8 3 4 13 7 14 6 8 5 10
8 6 3 4 2 5 6 3 4 2
5 6 3 4 15 11 9 8 4 9
8 4 10 3 2 7 14 15 9 10
3 2 7 9 10 7 6 5 9 10
11 12

As for maximum number of moves in optimal solution, at present there is known configuration that requires 80 moves. Moreover, as noted in [1], maximum number is not greater than 90 moves.

References

  1. "Searching with Pattern Databases" Joseph Culberson and Jonathan Schaeffer
    Department of Computer Science and University of Alberta
    URL: http://web.cs.ualberta.ca/~joe/Abstracts/15puzzle.html
  2. Article in November 2000 "C Magazine"
    URL: http://www.cmagazine.jp/contents/200011.html (Internet Archive Wayback Machine)

Postscript (4th April 2001)

A group of researchers from Switzerland (Adrian Brüngger, Ambros Marzetta, Komei Fukuda, Jurg Nievergelt) proved in 1997 that the 15 puzzle can be solved in 80 moves. These computations were carried out on the NEC Cenju-3 with from 64 up to 128 processors and took approximately three days which is the equivalent of 230 days of sequential CPU time.