Finding Optimal Solutions to the Twenty-Four Puzzle

Richard E. Korf, Larry A. Taylor

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.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.