Comparative Analysis of the Performance Testing Results of the Backtracking and Genetics Algorithm in Solving Sudoku Games
DOI:
https://doi.org/10.25139/ijair.v5i1.6501Keywords:
Puzzle Games, Sudoku Games, Backtracking Algorithm, Genetic AlgorithmAbstract
Games that hone thinking skills and logical accuracy have recently been very popular. One of them is the game Sudoku. Sudoku is a game that hones logic through puzzles arranged in rows and columns. Sudoku is also defined as a puzzle game that aims to arrange several numbers in a grid from one to nine on a grid consisting of 9x9 squares. The concept of this Sudoku game is to enter numbers into the rows and columns provided. The rule of this game is that the numbers arranged on the board cannot be the same in every row, column, and 3x3 square in the grid. In another sense, each number entered must appear once in each row and column. When running Sudoku, several numbers are already instructions for players to fill in the next boxes. The number of clues at the beginning of the game determines the difficulty level players face. The fewer clues, the more difficult the Sudoku is to solve. This study aims to compare how to solve Sudoku using genetic algorithms, backtracking, and the completion time needed. The tests' results show that the genetic and backtracking algorithms can solve Sudoku games quickly. Still, the backtracking algorithm has the advantage of being relatively shorter, and the process is not so complicated that the backtracking algorithm can be an alternative solution to solving Sudoku logic games.
References
K.A Putrilani et al, “Efektivitas Media Permainan Sudoku Dalam Menghafal Huruf Kana (Menggunakan Metode Eksperimen Quasi Terhadap Siswa Japanese Club SMP Laboratorium Percontohan UPI)â€, JAPANEDU, Vol. 1, No. 3, pp. 34-43, 2016.
F.A. Rahman; D. Anubhakti, “Implementasi Algoritma Backtracking Pada Permainan Sudokuâ€, MEANS (Media Informasi Analisa dan Sistem), Vol. 5, No.1, pp. 67-71, 2020.
D.S.Rahayu et al, “Evaluasi Algoritma Runut Balik dan Simulated Annealing pada Permainan Sudokuâ€, Jurnal Teknik Informatika dan Sistem Informasi, Vol. 3, No. 1, pp. 169-178, 2017.
K. Krisnandi; H. Agung, “Implementasi Algoritma Genetika untuk Memprediksi Waktu dan Biaya Pengerjaan Proyek Konstruksiâ€, Jurnal Ilmiah Fifo, Vol. 9, No. 2, pp. 90-97, 2017.
V.S. Widjaja; D.Z. Sudirman, “Implementasi Algoritma Backtracking Dengan Optimasi Menggunakan Teknik Hidden Single Pada Penyelesaian Permainan Sudokuâ€, Seminar Nasional Aplikasi Teknologi Informasi (SNATI), Yogyakarta, 15 Juni 2013, pp. 1-5, 2013.
C. Danuputri; N. Santosa, ““Aplikasi Pemecahan Soal Sudoku dengan Metode Backtracking†, Jurnal Informatika Universitas Pamulang, Vol. 6, No. 3, pp. 506-511, 2021.
A. Yusuf; Hendra, “Penyelesaian Puzzle Sudoku Menggunakan Algoritma Brute Force Dan Backtrackingâ€, Jurnal Techno Nusa Mandiri, Vol.X, No.1, pp. 207-215, 2013.
Herimanto et al, "An Implementation of Backtracking Algorithm for Solving A Sudoku-Puzzle Based on Android", Journal of Physics: Conference Series. https://doi.org/10.1088/1742-6596/1566/1/012038, pp. 1-6, 2019.
F. Utama, et al , “Implementasi Backtracking Algorithm Untuk Penyelesaian Permainan Su Doku Pola 9x9â€, Informatika Mulawarman : Jurnal Ilmiah Ilmu Komputer, Vol. 11, No. 1,pp. 29–36. https://doi.org/10.30872/jim.v11i1.200, 2017.
Afriyudi et al, “Penyelesaian Puzzle Sudoku menggunakan Algoritma Genetikâ€, Prosiding SNASTI, ISBN 978-979-89683-31-0.
A.A. Hanafi et al, â€Penyelesaian Permainan Sudoku Menggunakan Algoritma Backtracking Berbasis Artificial Intelligenceâ€. Jurnal ICTEE, Vol. 2, No. 2, E-ISSN : 2746-7481, Hal. 50-57, 2021.
Teneng et al, “Penerapan Algoritma Backtracking Pada Permainan Math Mazeâ€, Jurnal Informatika, Vol. 6, No 1, pp. 56-67, 2010.
H.S. Sulun; R. Muni, “Pembangkit Teka-Teki Silang Dengan Algoritma Backtracking Serta Aplikasi Permainannya Yang Berbasis Webâ€, Jurnal Informatika, Vol.4 No.2, pp. 457-466, 2010.
H.K. Tupan et al, “Optimasi Penempatan Load Break Switch (LBS) pada Penyulang Karpan 2 Ambon menggunakan Metode Algoritma Genetikaâ€, Jurnal EECCIS, Vol. 11, No. 1,pp. 1-8, 2017.
S.C. Sumarta, “Pengaruh Pengaturan Individu Proses Crossover Dan Mutasi Algoritme Genetika Pada Kasus Traveling Salesman Problemâ€, Jurnal Tematika, Vol. 4, No. 2, pp. 83-89, 2016.
M.E. Riadi, “Penggunaan Media Puzzle Untuk Meningkatkan Hasil Belajar Siswa Pada Tema Lingkungan Kelas Ii Sdn Jajartunggal III Surabayaâ€, JPGSD, Vol. 02, No. 02, pp. 1-11, 2014.
N. Nari et al, “Penerapan Permainan Puzzle Untuk Meningkatkan Kemampuan Membilangâ€, Jurnal Pembangunan dan Pendidikan: Fondasi dan Aplikasi, Vol.7, No. 1, pp. 44-52, 2019.
S. Sauri et al, “Pembuatan Media Pembelajaran Sudoku Puzzles Pada Materi Sistem Periodik Unsur†Gunung Djati Conference Series Seminar Nasional Tadris Kimiya 2020, Vol. 2, pp. 172-186, ISSN: 2774-6585, 2021.
Downloads
Published
How to Cite
Issue
Section
License
Authors who publish with International Journal of Artificial Intelligence & Robotics (IJAIR) agree to the following terms:
-
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License (CC BY-SA 4.0) 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.
