Solving the Sliding Puzzle problem using the A* algorithm and comparing the effectiveness of different heuristic functions
DOI:
https://doi.org/10.61173/rxef6g41Keywords:
- Sliding Puzzle, A* Algorithm, Heuristic Search, Manhattan Distance, Linear ConflictAbstract
This paper aims to solve the Sliding Puzzle problem using the A* algorithm and compare the effectiveness of different heuristic evaluation functions. Multiple heuristic functions including Manhattan Distance and Linear Conflict will be investigated. This helps to determine the best heuristic function of the A* algorithm by considering efficiency and accuracy.
References
[1] Archer, A. F. (1999). A Modern Treatment of the 15 Puzzle. The American Mathematical Monthly, 106(9), 793–799. https:// doi.org/10.1080/00029890.1999.12005124
[2] Spitznagel, E. L. (1967). A New Look at the Fifteen Puzzle. Mathematics Magazine, 40(4), 171–174. https://doi.org/10.1080/ 0025570X.1967.11975789
[3] Chapple, A., Croeze, A., Lazo, M., Merrill, H. An Analysis Dean&Francis Zike Qin, Mingfei Zhang of the 15-Puzzle. Louisiana State University. https://www.math. lsu.edu/system/files/RP1%20paper.pdf
[4] Setyobudhi, C. T. (2022). Comparison of A* Algorithm and Greedy Best Search in Searching Fifteen Puzzle Solution. International Journal of Innovation Scientific Research and Review, 04(07), 3094-3097. http://www.journalijisr.com/sites/ default/files/issues-pdf/IJISRR-941.pdf
[5] Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE transactions on Systems Science and Cybernetics, 4(2), 100-107. https://ieeexplore.ieee.org/document/4082128
[6] Korf, R. E. (1985). Depth-first iterative-deepening: An optimal admissible tree search. Artificial Intelligence, 27(1), 97-109. https://www.sciencedirect.com/science/article/abs/ pii/0004370285900840
Downloads
Published
Issue
Section
License
Copyright (c) 2025 by the authors.
This work is licensed under a Creative Commons Attribution 4.0 International License.
