Fast Search for Optimal Solutions of the Fifteen Puzzle Using Gap Sets

DOI Web Site 5 References
  • Yamamoto Osami
    Department of Information Engineering, Faculty of Science and Technology, Meijo University
  • Satone Hiroshi
    Department of Information Engineering, Graduate School of Science and Technology, Meijo University

Bibliographic Information

Other Title
  • ギャップ集合を用いた１５パズルの最適解探索の高速化

Abstract

The fifteen puzzle is a sliding puzzle which has fifteen pieces on which numbers from 1 to 15 are printed. Using the IDA* algorithm with an admissible evaluation function, we can obtain an optimal solution of the puzzle. The performance of the algorithm depends on the evaluation function. The most simple evaluation function is the Manhattan evaluation function, whose value is the sum of the Manhattan distances from the positions of the corresponding pieces in the goal configuration. In this paper, we propose an evaluation function whose values are greater than or equal to that of the Manhattan evaluation function. Our evaluation function refers an approximated database of the gap-2n set. The database is computed beforehand like pattern databases, but it is completely different from pattern databases. The belongingness of a configuration of pieces to the set has to be checked by the database. Using an evaluation function based on the gap-8 set, we were able to reduce the number of search nodes to about 2.5×10-4 times in average with the IDA* algorithm compared with the Manhattan evaluation function. We also show that combining an evaluation function by gap-8 set and an evaluation function by additive pattern databases of disjoint seven and eight pieces, we were able to reduce the number of search nodes by about 53 compared with the evaluation function only by the additive pattern databases.

Journal

References(5)*help

See more

Keywords

Details 詳細情報について

Report a problem

Back to top