Roy Mash San Francisco State University
For thirty years now the 8-puzzle, the most popular variant of the class of sliding block puzzles, has provided a popular test domain for the study of search algorithms, and the heuristic evaluations that aid them. Sliding block puzzles consist of a beginning arrangement, or start-state, of tiles and a single blank space. The object is to achieve a given arrangement, or goal-state, by successively sliding adjacent tiles into the blank area.
A complete solution of a sliding block puzzle is one which solves all (solvable) problem instances.
This talk summarizes some results of research that (1) develops an object-oriented design for easily and efficiently running complete solutions for sliding block puzzles, using different algorithms and heuristics; (2) extends the results of previous researchers to different types of goal-states, thus generating solutions which are 'exhaustively complete'; and (3) compares and contrasts some properties of 8-puzzle solutions with those of puzzles with different sizes and shapes.