On sliding block puzzles
F. Karlemo, Patric R. J. Östergård · 2000
A graph of a puzzle is obtained by associating each possible position with a vertex and by inserting edges between vertices iff the corresponding positions can be obtained from each other in one move. Computational methods for finding the vertices at maximum distance ffi 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 ffi for large puzzles are considered. Old results are surveyed, and a new upper bound for the 24-puzzle is obtained: ffi 210. 1. Introduction In the early 1980s, it was impossible to avoid hearing about Rubik's cube, a puzzle that became very popular all over the world. Very soon, mathematicians became interested in this puzzle, and several books have been written on the subject (for example, [4]). Another popular---and much older---puzzle is the 15-puzzle, which was invented by Sam Loyd in the 19th century. This puzzle, and its variants, will be consid...