Depth limited search for the 8-puzzle

Lee's algorithm is guaranteed to find the shortest path between two points, if such a path exists- provided the problem is tractable. If it is not, you will have to limit the search somehow, and hope for the best. Even though there is some scope for searching in the most promising direction first, sooner or later it will have to be depth limited search or iterative deepening search. This section uses the 8-puzzle for illustration.

You can move squares vertically or laterally in the 8-puzzle, but only to the free space, the goal being to get the board in the position shown. Some versions insist that the blank end up in the lower right corner, but this is hardly a different game.

Modern computers tend to blur the distinction between tractable and intractable problems: If you want a problem which really is still intractable, you can try the 15-puzzle.

My first try did not prevent revisiting and enjoyed a lookahead of 7 or 8 moves, so the results were not impressive: The success rate of 3% was too bad to be true, of course, and a prompt Internet search confirmed the suspicion: Half the initial positions are not solvable. Ergo, the real success rate was 6%, yet the site usually aims for 90% success in these projects.

After allowing a lookahead level of 29 and disabling revisiting, the more memory hungry program achieves a solution rate of 100%. The detailed results are in the following table: The program played 1,000 games and the (average) initial penalty score was 15.

Lookahead	Success (%)	Score after	Moves to win	Positions examined, games won	Positions examined, games lost
29	100	0	22	84504	-
26	96	.15	22	80532	160600
24	84	.64	21	68087	125010
22	66	1.4	21	49795	80116
20	47	2.3	22	32336	43582
15	18	4.7	23	6044	6284
10	5	7.5	19	3209	670
5	0.3	12	11	68	52

The low lookahead perfomance will be improved if you follow up on a few of the best intermediate positions, rather than just one. You may not get exactly the same figures if you use a different compiler, as the seed for the random number generator may be different: The 'add icon' section references a free C++ compiler. Here is the source code and binary file for this project.

At about ten puzzles per second on average and at the highest lookahead level, the speed looks quite reasonable on a rather modern (1.8 GHz) computer. However, if you wanted to solve a large number of puzzles and were short of time, 24 is probably a good compromise value.

It is better, of course, not to have to search at all: Ideally, a formula will yield a result, or at least an iterative procedure will improve an initial estimate.

The first version commandeered an exorbitant amount of memory, but this has been packed considerably in the second version (and executable file).

The digital storage oscilloscope shown last month needed an obvious correction to its schematic.

• Site map
• Digital storage oscilloscope (rudimentary)

For my own code up to this point: Valid XHTML 1.1