Completing Sudoku Games Using the Depth First Search Algorithm
DOI:
https://doi.org/10.33633/jais.v9i1.10017Abstract
Sudoku is a digital game that is included in the type of logic-based puzzle game where the goal is to fill in the puzzle with random numbers. Therefore, in this research it is proposed to use Artificial Intelligence which contains the Depth First Search Algorithm to track the number of possible solutions that lead to only one so that it becomes efficient. This game has different levels of difficulty such as easy, medium and difficult. The time and complexity of execution will vary depending on the difficulty so it is proposed to use Android Studio software. The experimental results prove that there is an increase in playing the Sudoku game quickly and accurately by applying the Depth First Search Algorithm method. This is proven by the ability to complete this game using the Depth First Search Algorithm using the Android Studio programming language. The average time at the easy level is 11:04 minutes, at the normal level is 10:52 minutes, at the hard level is 25:46 minutes, and at the extreme level is 38 minutes.References
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, p. 012038, Jun. 2020, doi: 10.1088/1742-6596/1566/1/012038.
H. Lloyd and M. Amos, “Solving Sudoku with Ant Colony Optimization,” IEEE Trans Games, vol. 12, no. 3, pp. 302–311, Sep. 2020, doi: 10.1109/TG.2019.2942773.
M. Praba, S. Radha, Priyam P. M., and B. S. Dhiya, “Sudoku Solver Using Minigrid Based Backtracking Algorithm,” International Journal of Research in Engineering, Science and Management, vol. 5, no. 6, pp. 138–140, 2022.
N. Kitsuwan, P. Pavarangkoon, H. M. Widiyanto, and E. Oki, “Dynamic load balancing with learning model for Sudoku solving system,” Digital Communications and Networks, vol. 6, no. 1, pp. 108–114, Feb. 2020, doi: 10.1016/j.dcan.2019.03.002.
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 Proceedings - 2020 International Seminar on Application for Technology of Information and Communication: IT Challenges for Sustainability, Scalability, and Security in the Age of Digital Disruption, iSemantic 2020, Institute of Electrical and Electronics Engineers Inc., Sep. 2020, pp. 548–553. doi: 10.1109/iSemantic50169.2020.9234267.
A. Z. Sevkli and K. A. Hamza, “General variable neighborhood search for solving Sudoku puzzles: unfiltered and filtered models,” Soft comput, vol. 23, no. 15, pp. 6585–6601, Aug. 2019, doi: 10.1007/s00500-018-3307-6.
R. Effendi, I. Gunawan, and Y. Efendi, “Software Design Completion of Sudoku Game with Branch and Bound Algorithm,” in International Multidisciplinary Conference on Education, Technology, and Engineering (IMCETE 2019), 2019, pp. 126–130.
C. M. Rodríguez-Peña, J. Ramón Martínez Batlle, and W. M. Maurer, “Correlation and Regression Analyses using Sudoku Grids,” International Journal of Science and Research, 2018, doi: 10.21275/ART2020922.
T. N. Lina and M. S. Rumetna, “Comparison Analysis of Breadth First Search and Depth Limited Search Algorithms in Sudoku Game,” Bulletin of Computer Science and Electrical Engineering, vol. 2, no. 2, pp. 74–83, Dec. 2021, doi: 10.25008/bcsee.v2i2.1146.
B. Vicky 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,” International Journal of Artificial Intelligence & Robotics (IJAIR), vol. 5, no. 1, pp. 29–35, 2023, doi: 10.25139/ijair.v5i1.6501.
H. R. R. Zaman and F. S. Gharehchopogh, “An improved particle swarm optimization with backtracking search optimization algorithm for solving continuous optimization problems,” Eng Comput, vol. 38, pp. 2797–2831, Oct. 2022, doi: 10.1007/s00366-021-01431-6.
Nurdin et al., “The Implementation of Backtracking Algorithm on Crossword Puzzle Games Based on Android,” in Journal of Physics: Conference Series, Institute of Physics Publishing, Nov. 2019. doi: 10.1088/1742-6596/1363/1/012075.
A. Candra, M. A. Budiman, and R. I. Pohan, “Application of A-Star Algorithm on Pathfinding Game,” in Journal of Physics: Conference Series, IOP Publishing Ltd, Jun. 2021. doi: 10.1088/1742-6596/1898/1/012047.
H. R. R. Zaman and F. S. Gharehchopogh, “An improved particle swarm optimization with backtracking search optimization algorithm for solving continuous optimization problems,” Eng Comput, vol. 38, pp. 2797–2831, Oct. 2022, doi: 10.1007/s00366-021-01431-6.
A. Agnesina, K. Chang, and S. K. Lim, “VLSI Placement Parameter Optimization using Deep Reinforcement Learning,” in IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD, Institute of Electrical and Electronics Engineers Inc., Nov. 2020. doi: 10.1145/3400302.3415690.
Downloads
Published
Issue
Section
License
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution 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 (See The Effect of Open Access).
