OPTIMIZATION OF BACKTRACKING ALGORITHM WITH HEURISTIC STRATEGY FOR LOGIC-BASED SORTING PUZZLE GAME SOLVING

  • Eka Qadri Nuranti Computer Science, Institut Teknologi Bacharuddin Jusuf Habibie, Indonesia
  • Naili Suri Intizhami Computer Science, Institut Teknologi Bacharuddin Jusuf Habibie, Indonesia
  • Primadina Hasanah Mathematical Science, University of Liverpool, United Kingdom
Keywords: backtracking algorithm, game, heuristic, lookahead, puzzle, sorting

Abstract

Puzzle Game Sorting is a logic-based puzzle game where players must transfer colored balls into tubes until each tube contains only one color. Although it appears simple, the game becomes increasingly challenging at higher levels, testing players’ logical thinking and patience. This study proposes using the backtracking algorithm combined with optimization strategies, such as conflict heuristics and lookahead, to address players’ challenges at advanced levels. The test results indicate that the optimized backtracking algorithm can solve the game faster and with more efficient steps compared to manual methods. Specifically, heuristic optimization strategies significantly improved performance, reducing execution time by up to 91.4% and the number of steps by up to 76.9% at the most complex levels. These findings demonstrate that combining the backtracking algorithm and optimization strategies is an effective solution for solving puzzles in Sorting, particularly at levels with increasing complexity.

Downloads

Download data is not yet available.

References

N. A. Hasanah, L. Atikah, D. Herumurti, and A. A. Yunanto, “A Comparative Study: Ant Colony Optimization Algorithm and Backtracking Algorithm for Sudoku Game,” in *2020 International Seminar on Application for Technology of Information and Communication (iSemantic)*, Semarang, Indonesia: IEEE, Sep. 2020, pp. 548–553. doi: 10.1109/iSemantic50169.2020.9234267.

N. Nurdin, R. Suhartono, and T. Wibowo, “The Implementation of Backtracking Algorithm on Crossword Puzzle Games Based on Android,” *J. Phys.: Conf. Ser.*, vol. 1363, no. 1, p. 012075, Nov. 2019, doi: 10.1088/1742-6596/1363/1/012075.

T. Ito, H. Nakamura, and K. Tanaka, “Sorting balls and water: Equivalence and computational complexity,” *Theoretical Computer Science*, vol. 978, p. 114158, Nov. 2023, doi: 10.1016/j.tcs.2023.114158.

D. Chen, F. Zou, R. Lu, and S. Li, “Backtracking search optimization algorithm based on knowledge learning,” *Information Sciences*, vol. 473, pp. 202–226, Jan. 2019, doi: 10.1016/j.ins.2018.09.039.

M. Esteve, J. J. Rodriguez-Sala, J. J. Lopez-Espin, and J. Aparicio, “Heuristic and Backtracking Algorithms for Improving the Performance of Efficiency Analysis Trees,” *IEEE Access*, vol. 9, pp. 17421–17428, 2021, doi: 10.1109/ACCESS.2021.3054006.

P. Garg, A. Jha, and K. A. Shukla, “Randomised Analysis of Backtracking-based Search Algorithms in Elucidating Sudoku Puzzles Using a Dual Serial/Parallel Approach,” in *Inventive Computation and Information Technologies*, vol. 336, S. Smys, V. E. Balas, and R. Palanisamy, Eds., Singapore: Springer Nature Singapore, 2022, pp. 281–295. doi: 10.1007/978-981-16-6723-7_21.

V. Vidal, “A Lookahead Strategy for Heuristic Search Planning,” 2004.

M. N. I. Siddique, M. J. Rana, M. Shafiullah, S. Mekhilef, and H. Pota, “Automating distribution networks: Backtracking search algorithm for efficient and cost-effective fault management,” *Expert Systems with Applications*, vol. 247, p. 123275, Aug. 2024, doi: 10.1016/j.eswa.2024.123275.

A. Mehmood, P. Shi, M. A. Z. Raja, A. Zameer, and N. I. Chaudhary, “Design of backtracking search heuristics for parameter estimation of power signals,” *Neural Comput & Applic.*, vol. 33, no. 5, pp. 1479–1496, Mar. 2021, doi: 10.1007/s00521-020-05029-9.

K. Okumura, M. Machida, X. Défago, and Y. Tamura, “Priority inheritance with backtracking for iterative multi-agent path finding,” *Artificial Intelligence*, vol. 310, p. 103752, Sep. 2022, doi: 10.1016/j.artint.2022.103752.

S. Nofal, K. Atkinson, and P. E. Dunne, “Looking-ahead in backtracking algorithms for abstract argumentation,” *International Journal of Approximate Reasoning*, vol. 78, pp. 265–282, Nov. 2016, doi: 10.1016/j.ijar.2016.07.013.

F. Gebali, M. Taher, A. M. Zaki, M. W. El-Kharashi, and A. Tawfik, “Parallel Multidimensional Lookahead Sorting Algorithm,” *IEEE Access*, vol. 7, pp. 75446–75463, 2019, doi: 10.1109/ACCESS.2019.2920917.

M. Zhang and J. Lucas, “Lookahead Optimizer: k steps forward, 1 step back,” *33rd Conference on Neural Information Processing Systems*, 2019.

J. A. Abdulsaheb and D. J. Kadhim, “Classical and Heuristic Approaches for Mobile Robot Path Planning: A Survey,” *Robotics*, vol. 12, no. 4, p. 93, Jun. 2023, doi: 10.3390/robotics12040093.

M. D. Pratama, R. Abdillah, D. Herumurti, and S. C. Hidayati, “Algorithmic Advancements in Heuristic Search for Enhanced Sudoku Puzzle Solving Across Difficulty Levels,” vol. 5, no. 4, 2024.

Published
2025-01-04
How to Cite
[1]
E. Q. Nuranti, N. S. Intizhami, and P. Hasanah, “OPTIMIZATION OF BACKTRACKING ALGORITHM WITH HEURISTIC STRATEGY FOR LOGIC-BASED SORTING PUZZLE GAME SOLVING”, J. Tek. Inform. (JUTIF), vol. 5, no. 6, pp. 1883-1892, Jan. 2025.