ANALISIS PERBANDINGAN ALGORITMA DEPTH FIRST SEARCH DAN ALGORITMA BACKTRACKING DALAM PENYELESAIAN PERMAINAN SUDOKU - Saragih, Adinda Boru; Prihandono, Bayu; Pasaribu, Meliana (FMIPA Universitas Tanjungpura, 2025)
Sudoku adalah permainan dengan jenis teka-teki logika berbentuk nÃ—n, yang terdiri dari baris, kolom, grid dan kotak. Kotak-kotak tersebut diisi dengan angka tanpa ada pengulangan dalam satu grid, baris atau kolom. Sudoku memiliki tingkat kesulitan yang berbeda, mulai dari tingkat sangat mudah hingga sangat sulit. Petunjuk angka yang diberikan setidaknya memiliki minimal 17 angka. Untuk menyelesaikan permainan sudoku dengan waktu yang lebih sedikit, diperlukan algoritma pencarian yang tepat. Dalam penelitian ini digunakan algoritma Depth First Search (DFS) dan Backtracking untuk melakukan penelusuran solusi dengan bantuan pohon berakar. Tujuan penelitian ini untuk membandingkan algoritma DFS dan Backtracking dalam menyelesaikan permainan sudoku. Penelitian ini menggunakan Sudoku berukuran 9Ã—9 pada tingkat sulit, dari aplikasi Sudoku versi 4.6.0 dengan 54 kotak kosong yang harus diselesaikan. Penelusuran solusi menunjukkan DFS membutuhkan sebanyak 249 langkah dan 70 iterasi, sedangkan Backtracking membutuhkan 173 langkah dan 25 iterasi untuk mendapatkan solusi secara keseluruhan. Setelah dilakukan sebanyak 20 kali percobaan dengan Python, hasil percobaan menunjukkan, DFS membutuhkan rata-rata 61.443 langkah dan 6.828 iterasi dengan waktu eksekusi 0,408114 detik, sedangkan algoritma Backtracking hanya memerlukan rata-rata 17.970 langkah dan 2.021 iterasi, dengan waktu eksekusi 0,024750 detik. Perbedaan ini menunjukkan algoritma Backtracking lebih efisien dibandingkan algoritma DFS untuk menyelesaikan permasalahan sudoku pada penelitian ini. Dilakukan percobaan tambahan pada beberapa permasalahan sudoku berdasarkan tingkat kesulitannya, sebanyak 10 kali. Hasilnya menunjukkan algoritma Backtracking konsisten lebih cepat dalam eksekusi waktu dibandingkan DFS, meskipun DFS memerlukan lebih sedikit langkah dan iterasi. Ini menunjukkan Backtracking lebih efisien dalam menyelesaikan sudoku.