Adem Tuncer‡Corresponding author: Adem Tuncer ( adem.tuncer@yalova.edu.tr ) © Adem Tuncer. This is an open access article distributed under the terms of the Creative Commons Attribution License (CC BY-ND 4.0). This license allows reusers to copy and distribute the material in any medium or format in unadapted form only, and only so long as attribution is given to the creator. The license allows for commercial use. Citation:
Tuncer A (2021) 15-Puzzle Problem Solving with the Artificial Bee Colony Algorithm Based on Pattern Database. JUCS - Journal of Universal Computer Science 27(6): 635-645. https://doi.org/10.3897/jucs.65202 |  |
The N-puzzle problem is one of the most classical problems in mathematics. Since the number of states in the N-puzzle is equal to the factorial of the number of tiles, traditional algorithms can only provide solutions for small-scale ones, such as 8-puzzle. Various uninformed and informed search algorithms have been applied to solve the N-puzzle, and their performances have been evaluated. Apart from traditional methods, artificial intelligence algorithms are also used for solutions. This paper introduces a new approach based on a meta-heuristic algorithm with a solving of the 15-puzzle problem. Generally, only Manhattan distance is used as the heuristic function, while in this study, a linear conflict function is used to increase the effectiveness of the heuristic function. Besides, the puzzle was divided into subsets named pattern database, and solutions were obtained for the subsets separately with the artificial bee colony (ABC) algorithm. The proposed approach reveals that the ABC algorithm is very successful in solving the 15-puzzle problem.