Algorithmic Advancements in Heuristic Search for Enhanced Sudoku Puzzle Solving Across Difficulty Levels - Pratama, Moch Deny; Abdillah, Rifqi; Herumurti, Darlis; Hidayati, Shintami Chusnul (Building of Informatics, Technology and Science (BITS), 2024)
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