We have found the first optimal solutions to random instances of the Twenty-Four Puzzle, the 5 x 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.
Registration: ISBN 978-0-262-51091-2
Copyright: August 4-8, 1996, Portland, Oregon. Published by The AAAI Press, Menlo Park, California.