Finding Optimal Solutions to the Twenty-Four Puzzle

Abstract

We have found the first optimal solutions to a complete set of random instances of the Twenty-Four Puzzle, the 5 \\Theta 5 version of the well-known sliding-tile puzzles. Our new contribution to this problem is a more powerful admissible heuristic function. We present a general theory for the automatic discovery of such heuristics, which is based on considering multiple subgoals simultaneously. In addition, we apply a technique for pruning duplicate nodes in depth-first search using a finite-state machine. Finally, we observe that as heuristic search problems are scaled up, more powerful heuristic functions become both necessary and cost-effective. Introduction The sliding-tile puzzles, such as the Eight and Fifteen Puzzle, have long served as testbeds for heuristic search in AI. A square frame is filled with numbered tiles, leaving one position empty, called the blank. Any tile that is horizontally or vertically adjacent to the blank can be slid into the blank position. The task is to...