Complete Solution of the Eight-Puzzle and the Benefit of Node Ordering in IDA

Abstract

The 8-puzzle is the largest puzzle of its type that can be completely solved. It is simple, and yet obeys a combinatorially large problem space of 9!=2 states. The N \\Theta N extension of the 8-puzzle is NP-hard. In the first part of this paper, we present complete statistical data based on an exhaustive evaluation of all possible tile configurations. Our results include data on the expected solution lengths, the `easiest' and `worst' configurations, and the density and distribution of solution nodes in the search tree. In our second set of experiments, we used the 8-puzzle as a workbench model to evaluate the benefit of node ordering schemes in IterativeDeepening A* (IDA*). One highlight of our results is that almost all IDA* implementations perform worse than would be possible with a simple random ordering of the operators. 1 Introduction The 8-puzzle is a prominentworkbench model for measuring the performance of heuristic search algorithms [ Gaschnig, 1979# Nilsson, 1980# Pearl, 19...