SLIDING-TILE PUZZLES AND RUBIK'S CUBE IN AL RESEARCH
Richard E. Korf · IEEE Intelligent Systems and their Applications · 1999
The best-known sliding-tile puzzle is the Fifteen Puzzle, shown in Figure 1a. Other sizes include the 3 × 3 Eight Puzzle and the 5 × 5 Twenty-Four Puzzle. The standard 3 × 3 × 3 Rubik’s Cube (see Figure 1b) also comes in 2 × 2 × 2, 4 × 4 × 4, and 5 × 5 × 5 versions. Both these puzzles had similar histories, about 100 years apart. Finding optimal or shortest solutions to these puzzles has spawned important results in space-efficient search algorithms and admissible heuristic functions.