On Sliding Block Puzzles

Abstract

A graph of a puzzle is obtained by associating each possible position with a vertex and by inserting edges between vertices if and only if the corresponding positions can be obtained from each other in one move. Computational methods for finding the vertices at maximum distance $\delta$ from a vertex associated with a goal position are presented. Solutions are given for small sliding block puzzles, and methods for obtaining upper and lower bounds on $\delta$ for large puzzles are considered. Old results are surveyed, and a new upper bound for the 24-puzzle is obtained: $\delta \le 210$.