Penyelesaian Permainan Sudoku Menggunakan Algoritma Backtracking Berbasis Artificial Intelligence

Abstract

Kebutuhan teknologi untuk mempermudah dan menyelesaikan suatu permasalahan menjadi efisien sangat diperlukan di era modern ini. Salah satu bidang ilmu yang sering digunakan untuk memecahkan masalah dengan meniru kebiasaan manusia adalah Artificial Intelligence (AI). Permainan Sudoku merupakan permainan dengan jenis teka teki logika. Sudoku termasuk pada permasalahan NP – complete, sehingga sulit atau bahkan tidak bisa untuk diselesaikan dengan waktu yang sama. Dari permasalahan tersebut, dibutuhkan sebuah algoritma AI untuk menyelesaikan Permainan Sudoku. Salah satu algoritmanya adalah Backtracking (runut-balik). Hasil percobaan menunjukkan semakin banyak jumlah proses backtracking berbanding lurus dengan semakin banyaknya waktu yang dibutuhkan untuk menyelesaikan permainan Puzzel Sudoku. Kemudian, tingkat akurasi pada program sudoku solving dengan algortima backtracking mencapai 100% dengan kotak kosong berjumlah 43.