IDA15

IDA15 is a freeware program which solves the fifteen puzzle in the fewest number of moves possible. I have provided both an executable which runs under 32-bit Microsoft Windows  from a DOS box and C++ source code using only standard C library calls. The executable is capable of examining 1.2 million puzzle configurations per second on an Intel 166 MHz Pentium with MMX using EDO memory. It usually takes only a few seconds to find a solution. About 10 megabytes of memory are required in addition to the amount used by the operating system. Click here to download IDA15.
 

How It Works

IDA15 uses the algorithm known as Iterative Deepening A* Search (IDA*) to solve the fifteen puzzle (see [2]). IDA* search is guided by a heuristic function which is a lower-bound estimate of the number of moves required to solve any given configuration of the puzzle. Let n be the heuristic estimate of the initial configuration of the puzzle. IDA* proceeds with an exhaustive depth-first search of all sequences of moves of length n. If a solution is not found, the search is repeated for moves of length n+1 and so on until a solution is found. (IDA15 actually increments by 2 every iteration since the position of the blank tile indicates whether the solution requires an even or odd number of moves.) Each depth-first search iteration is narrowed considerably using the heuristic estimate as follows: Let n be the length of the solution we're searching for in the current iteration. Now, suppose we encounter a node in the search tree which is m moves away from the initial configuration and the heuristic function estimates there are at least h moves required to solve the node's configuration. If m+h>n, there is no need to explore this node further in this iteration, since all solutions passing through this node would be too long.

The heuristic function used by IDA15 is the sum of Disjoint Pattern Databases (see [1] and [4]). Two databases are used. The first is a table indexed by the positions of the tiles 11, 12, 15 and blank, with 43,680 entries of 1 byte each. Each entry stores the minimum number of moves (counting only moves involving the tiles 11, 12 and 15) required to move all four tiles (including the blank) into their home positions. The second database is similar to the first, but is indexed by the tiles 1, 2, 5, 6 and blank. Thus, it has 524,160 entries of 1 byte each. This table is also used for the tiles 3, 4, 7, 8 and blank using a horizontal reflection and the tiles 9, 10, 13, 14 and blank using a vertical reflection. (The fact that the reflections move the home position of the blank tile does not cause a problem, since the blank can be moved back to its home position without disturbing any of the other tiles of the pattern once they are in their home positions.) The total heuristic function is the sum of the look-up in the first database and the three look-ups in the second database. Thus, IDA15's heuristic is always at least the sum of Manhattan Distance + Last Move + Corner heuristics (see [3]). In fact, it also includes 14 out of 42 linear conflicts and more conflicts are possible. Empirically, IDA15 searches fewer nodes than Manhattan Distance + Linear Conflicts, with each node requiring about half the time.
 

References

  1. Culberson, J.C., and J. Schaeffer, Searching with pattern databases, Proceedings of the 11th Conference of the Canadian Society for the Computational Study of Intelligence, published in Advances in Artificial Intelligence, Gordon McCalla (Ed.), Springer Verlag, 1996.
  2. Korf, R. E., Depth-first iterative-deepening: An optimal admissable tree search, Artificial Intelligence, Vol. 27, No. 1, 1985, pp. 97-109.
  3. Korf, R. E., and L.A. Taylor, Finding optimal solutions to the twenty-four puzzle, Proceedings of AAAI-96, Portland, OR, Aug. 1996, pp. 1202-1207.
  4. Korf, R. E., Recent progress in the design and analysis of admissible heuristic functions, Proceedings of AAAI-2000,  pp. 1165-1170.

Contact

Robert Hilchie, aa576@freenet.carleton.ca