Affordable Access

Efficiently Searching the 15-Puzzle

Authors
Publisher
University of Alberta
Publication Date
Keywords
  • A* Algorithm
  • Iterative Deepening Improvement
  • Algorithm Efficiency
Disciplines
  • Computer Science

Abstract

Technical report TR94-08. The A* algorithm for single-agent search has attracted considerable attention in recent years due to Korf's iterative deepening improvement (IDA*). The algorithm's efficiency depends on the quality of the lower bound estimates of the solution cost. For sliding tile puzzles, reduction databases are introduced as a means of improving the lower bound. The database contains all solutions to the subproblem of correctly placing N tiles. For the 15-Puzzle, IDA* with reduction databases (N=8) are shown to reduce the total number of nodes searched on a standard problem set of 100 positions by over 1000-fold. With the addition of transposition tables and endgame databases, an improvement of over 1700-fold is seen.

There are no comments yet on this publication. Be the first to share your thoughts.