Implementasi Gabungan Algoritma Backtracking dan Simulated Annealing untuk Menyelesaikan Puzzle Sudoku

Abstract

A Sudoku puzzle is a popular type of game that can be viewed as a combinatorial problem. This study proposes a solution to Sudoku by hybridizing Backtracking and Simulated Annealing algorithms. The Backtracking algorithm is used to generate an initial solution for the puzzle. This solution is then improved using the Simulated Annealing algorithm, which creates neighboring solutions by swapping cell contents, excluding the clue numbers. The temperature in the algorithm is gradually decreased until no violations remain. Test results indicate that this hybrid of algorithms can effectively solve Sudoku puzzles up to 20x20 in size. Specifically, for the 20x20 puzzles, the proposed approach requires a shorter computation time compared to using the Backtracking or Simulated Annealing algorithms individually. These findings suggest that the hybrid of Backtracking and Simulated Annealing algorithms is an effective alternative for solving Sudoku puzzles.

Keywords: Backtracking, Optimization, Simulated annealing, Sudoku

Puzzle Sudoku adalah salah satu jenis permasalahan kombinatorial yang dapat diselesaikan menggunakan berbagai metode pencarian solusi. Algoritma Backtracking adalah metode yang umum digunakan karena jaminan didapatkannya solusi optimal meskipun kurang efisien untuk puzzle berukuran besar. Di sisi lain, Algoritma Simulated Annealing mampu mencari solusi optimal dengan cepat, akan tetapi bergantung pada solusi awalnya. Penelitian ini mengusulkan algoritma gabungan antara Algoritma Backtracking dan Simulated Annealing untuk meningkatkan efisiensi dalam menyelesaikan Puzzle Sudoku. Proses penyelesaian dimulai dengan menentukan parameter-parameter Simulated Annealing, diikuti dengan pengisian sebagian puzzle menggunakan Algoritma Backtracking. Sel kosong yang tersisa diisi dengan angka acak, kemudian dievaluasi jumlah pelanggarannya berdasarkan aturan Puzzle Sudoku. Selanjutnya, proses pencarian solusi optimal dilakukan dengan menukar isi sel selain angka petunjuk dan menurunkan temperatur secara bertahap hingga tidak ada pelanggaran yang tersisa. Hasil pengujian menunjukkan bahwa pendekatan gabungan kedua algoritma ini mampu menyelesaikan Puzzle Sudoku secara optimal dengan waktu komputasi yang lebih singkat dalam menyelesaikan Sudoku berukuran  dibandingkan dengan penggunaan Algoritma Backtracking atau Simulated Annealing yang dilakukan secara terpisah. Pendekatan ini menjadikannya alternatif yang efektif dalam pemecahan teka-teki Sudoku secara optimal.