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.
