Algorithmic Advancements in Heuristic Search for Enhanced Sudoku Puzzle Solving Across Difficulty Levels
-
Moch Deny Pratama
*
Institut Teknologi Sepuluh Nopember, Surabaya,
Indonesia
- Rifqi Abdillah Institut Teknologi Sepuluh Nopember, Surabaya, Indonesia
- Darlis Herumurti Institut Teknologi Sepuluh Nopember, Surabaya, Indonesia
- Shintami Chusnul Hidayati Institut Teknologi Sepuluh Nopember, Surabaya, Indonesia (*) Corresponding Author
Abstract
Computer technology, particularly artificial intelligence, has found diverse applications in the rapidly evolving era of the industrial revolution, notably in gaming, delving into artificial intelligence and explicitly applying game-solving techniques to Sudoku puzzles. Sudoku, a popular game requiring logical precision, serves as an ideal platform for exploring algorithms such as depth-first search, breadth-first search, and heuristic search. This research identifies memory-intensive demands in breadth-first search and the potential issue of infinite traversal in depth-first search. To address these challenges, the study proposes implementing the heuristic search algorithm, which prioritizes promising paths based on estimations of proximity to the goal state made by a heuristic function. The primary objective is to enhance Sudoku puzzle-solving by comparing the performance of the heuristic search algorithm with traditional breadth-first and depth-first search methods, with a particular focus on improving efficiency and reducing memory usage, including time and steps. The results indicate that the heuristic search algorithm outperforms traditional methods, demonstrating faster completion times and reduced memory requirements, thereby contributing to the advancement of Sudoku-solving algorithms. The study evaluates their performance across different difficulty levels, utilizing data from sudoku.com and extremesudoku.info. Notably, the heuristic search algorithm emerges as a superior method, outperforming other algorithms in terms of completion steps and time efficiency. The implementation and analysis involved three types of Sudoku puzzle-solving methods, revealing that the heuristic search algorithm significantly outperforms other algorithms, optimizing its performance in solving Sudoku puzzles. The average time required to complete Sudoku puzzles from data sourced from Sudoku.com was 0.02, 0.05, and 0.61 seconds for each level, respectively. In contrast, according to extremesudoku.info, it took 0.31 seconds for the highest difficulty level. Furthermore, the average total steps needed on sudoku.com ranged from 43 to 1201 steps for each level, spanning from easy to hard. On extremesudoku.info, 509 steps were required for the highest difficulty level. These results affirm the reliability of heuristic search, consistently demonstrating encouraging outcomes and outperforming other algorithms across diverse conditions. This strategic selection facilitates a comprehensive analysis of Sudoku problem-solving algorithms, allowing for the exploration of algorithmic performance and providing a comprehensive range of Sudoku puzzles, thereby ensuring the study's robustness and validity
Downloads
References
A. Jungherr and D. B. Schlarb, “The extended reach of game engine companies: How companies like epic games and Unity technologies provide platforms for extended reality applications and the metaverse,” Soc. Media+ Soc., vol. 8, no. 2, p. 20563051221107640, 2022.
Herimanto, P. Sitorus, and E. M. Zamzami, “An Implementation of Backtracking Algorithm for Solving A Sudoku-Puzzle Based on Android,” J. Phys. Conf. Ser., vol. 1566, no. 1, 2020, doi: 10.1088/1742-6596/1566/1/012038.
B. de Kegel and M. Haahr, “Procedural puzzle generation: A survey,” IEEE Trans. Games, vol. 12, no. 1, pp. 21–40, 2020, doi: 10.1109/TG.2019.2917792.
B. V. Indriyono, N. Pamungkas, Z. Pratama, E. Mintorini, I. Dimentieva, and P. Mellati, “Comparative Analysis of the Performance Testing Results of the Backtracking and Genetics Algorithm in Solving Sudoku Games,” vol. 5, no. 1, pp. 29–35, 2023.
A. Narayanaswamy and P. Shrivastava, “Image Detection and Digit Recognition to solve Sudoku as a Constraint Satisfaction Problem,” 2019.
R. H. Chae and A. C. Regan, “An analysis of Harmony Search for solving Sudoku puzzles,” Soft Comput. Lett., vol. 3, p. 100017, 2021.
C. Wang et al., “A Novel Evolutionary Algorithm with Column and Sub-Block Local Search for Sudoku Puzzles,” IEEE Trans. Games, vol. PP, pp. 1–11, 2023, doi: 10.1109/TG.2023.3236490.
R. Rahim, R. Dijaya, M. T. Multazam, A. D. Gs, and D. Sudrajat, “Puzzle game solving with breadth first search algorithm,” J. Phys. Conf. Ser., vol. 1402, no. 6, 2019, doi: 10.1088/1742-6596/1402/6/066040.
H. Lloyd and M. Amos, “Solving Sudoku with Ant Colony Optimization,” IEEE Trans. Games, vol. 12, no. 3, pp. 302–311, 2020, doi: 10.1109/TG.2019.2942773.
T. Cazenave, “Monte Carlo Game Solver,” 2020, doi: 10.1007/978-3-030-89453-5_5.
T. H. Lim and P. L. Ng, “Evaluating recursive backtracking depth-first search algorithm in unknown search space for self-learning path finding robot,” in Artificial Intelligence for Communications and Networks: Second EAI International Conference, AICON 2020, Virtual Event, December 19-20, 2020, Proceedings 2, Springer, 2021, pp. 531–543.
R. Jain and M. Patel, “Investigating the Impact of Different Search Strategies (Breadth First, Depth First, A*, Best First, Iterative Deepening, Hill Climbing) on 8-Puzzle Problem Solving-A Case Study,” IJSDR2302112 Int. J. Sci. Dev. Res., 2023.
H. Wen and W. Zhang, “Improving Parallelism of Breadth First Search (BFS) Algorithm for Accelerated Performance on GPUs,” in 2019 IEEE High Performance Extreme Computing Conference (HPEC), IEEE, 2019, pp. 1–7.
J. Li, “Efficient and Effective Techniques for Large-Scale Multi-Agent Path Finding.” University of Southern California, 2022.
A. Shafique, F. Sohail, and A. I. Qadri, “Comparative Analysis of Search Algorithms in AI,” no. October, 2022, doi: 10.13140/RG.2.2.29282.61123.
“Sudoku Data Source (extremesudoku.info).” [Online]. Available: https://extremesudoku.info/
“Sudoku Data Source (sudoku.com).” [Online]. Available: https://sudoku.com/
T. Sasaki, D. Miyahara, T. Mizuki, and H. Sone, “Efficient card-based zero-knowledge proof for Sudoku,” Theor. Comput. Sci., vol. 839, pp. 135–142, 2020, doi: 10.1016/j.tcs.2020.05.036.
K. Khanchandani, A. Pandey, S. Khan, M. Patil, and R. Rajan, “Automated Sudoku Analyser,” Asian J. Converg. Technol., vol. V, no. I, pp. 1–7, 2019.
J. Luo, “Exploring Robot Morphology Spaces through Breadth-First Search and Random Query,” arXiv Prepr. arXiv2309.14387, 2023.
A. B. Matos, “The most difficult Sudoku puzzles are quickly solved by a straightforward depth-first search algorithm,” 2016, [Online]. Available: https://www.dcc.fc.up.pt/~acm/sudoku.pdf
D. Chen, Y. Bai, W. Zhao, S. Ament, J. M. Gregoire, and C. P. Gomes, “Deep reasoning networks for unsupervised pattern de-mixing with constraint reasoning,” 37th Int. Conf. Mach. Learn. ICML 2020, vol. PartF16814, pp. 1477–1486, 2020.
Y. Björnsson, S. Helgason, and A. Pálsson, “Searching for Explainable Solutions in Sudoku,” IEEE Conf. Games, 2021.
Y. Wu and H. Nakayama, “Graph-Based Heuristic Search for Module Selection Procedure in Neural Module Network,” Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), vol. 12624 LNCS, pp. 560–575, 2021, doi: 10.1007/978-3-030-69535-4_34.
V. Maniezzo, T. Stützle, and S. Voß, Matheuristics. Springer, 2021.
M. Elbes, S. Alzubi, T. Kanan, A. Al-Fuqaha, and B. Hawashin, “A survey on particle swarm optimization with emphasis on engineering and network applications,” Evol. Intell., vol. 12, pp. 113–129, 2019.
B. Cserna, W. J. Doyle, J. S. Ramsdell, and W. Ruml, “Avoiding dead ends in real-time heuristic search,” 32nd AAAI Conf. Artif. Intell. AAAI 2018, pp. 1306–1313, 2018.
Bila bermanfaat silahkan share artikel ini
Berikan Komentar Anda terhadap artikel Algorithmic Advancements in Heuristic Search for Enhanced Sudoku Puzzle Solving Across Difficulty Levels
Pages: 659−6671
Copyright (c) 2024 Moch Deny Pratama, Rifqi Abdillah, Darlis Herumurti, Shintami Chusnul Hidayati
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under Creative Commons Attribution 4.0 International License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (Refer to The Effect of Open Access).
