Usage
  • 816 views
  • 599 downloads

Efficiently Searching the 15-Puzzle

  • Author(s) / Creator(s)
  • 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. | TRID-ID TR94-08

  • Date created
    1994
  • Subjects / Keywords
  • Type of Item
    Report
  • DOI
    https://doi.org/10.7939/R3KR2G
  • License
    Attribution 3.0 International