Usage
  • 85 views
  • 61 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