Comparative Analysis of the Performance Testing Results of the Backtracking and Genetics Algorithm in Solving Sudoku Games

Bonifacius Indriyono; Natalinda  Pamungkas; Zudha  Pratama; Ery  Mintorini; Imelda  Dimentieva; Pita  Mellati

doi:10.25139/ijair.v5i1.6501

Bonifacius Indriyono Information System Department, Universitas Dian Nuswantoro http://orcid.org/0000-0001-8805-9047
Natalinda Pamungkas Information System Department, Universitas Dian Nuswantoro
Zudha Pratama Informatics Department, Universitas Dian Nuswantoro
Ery Mintorini Visual Communication Design, Universitas Dian Nuswantoro
Imelda Dimentieva Information System Department, Universitas Dian Nuswantoro
Pita Mellati Information System Department, Universitas Dian Nuswantoro

https://doi.org/10.25139/ijair.v5i1.6501

Abstract views: 355 ,

PDF downloads: 245

Keywords: Puzzle Games, Sudoku Games, Backtracking Algorithm, Genetic Algorithm

Abstract

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.

Downloads

Download data is not yet available.

Author Biographies

Bonifacius Indriyono, Information System Department, Universitas Dian Nuswantoro

Natalinda Pamungkas, Information System Department, Universitas Dian Nuswantoro

Zudha Pratama, Informatics Department, Universitas Dian Nuswantoro

Ery Mintorini, Visual Communication Design, Universitas Dian Nuswantoro

Imelda Dimentieva, Information System Department, Universitas Dian Nuswantoro

Pita Mellati, Information System Department, Universitas Dian Nuswantoro

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.