Experiments with Sliding Block Puzzles

Wednesday, March 12, 2003 - 17:30
TH 331
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.

Roy Mash received his BA in English from the Univ or Michigan (1972), MA in Philosophy from San Francisco State Univ (1987), MS in Computer Science from San Francisco State Univ (2002). His research interests include algorithms, heuristic search, and computer languages. This lecture derives from his recent Masters Thesis at San Francisco State University.