Completing Sudoku Games Using the Depth First Search Algorithm

Fauzan Maulana Alfany, Christy Atika Sari, Cahaya Jatmoko, Deddy Award Widya Laksana, Candra Irawan, Solichul Huda

Abstract


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.


Full Text:

PDF

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.




DOI: https://doi.org/10.33633/jais.v9i1.10017

Article Metrics

Abstract view : 0 times
PDF - 0 times

Refbacks

  • There are currently no refbacks.


Flag Counter

 

 

 

 

Journal of Applied Intelligent System (e-ISSN : 2502-9401, p-ISSN : 2503-0493) is published by Department of Informatics Universitas Dian Nuswantoro Semarang and IndoCEISS.

  

 

Journal of Applied Intelligent System indexed by :


This journal is under licensed of Creative Commons Attribution 4.0 International License.

Visitor Stats