Finding Optimal Solutions to the Twenty-Four Puzzle

Proceedings of the AAAI Conference on Artificial Intelligence, 13

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 13

Search

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.