ABSTRAKSI: Su Doku adalah permainan mengasah otak yang dipopulerkan oleh bangsa Jepang. Angka-angka dimasukkan ke dalam kotak bujur sangkar 9 x 9 dan tidak boleh terdapat angka yang sama pada tiap baris dan kolom.
Dalam Tugas Akhir yang berjudul “Analisis Perbandingan Algoritma Backtracking dan Dancing Links Dalam Domain Waktu dan Memori Untuk Penyelesaian Permasalahan Su Doku” ini dianalisa dua algoritma berbeda, yaitu Backtracking dan Dancing Links. Kedua algoritma tersebut dihitung kompleksitasnya secara manual, kemudian dibandingkan kinerjanya dalam menyelesaikan puzzle Su Doku. Hasil dua jenis perbandingan akan dilihat dukungannya satu sama lain sehingga diperoleh kesimpulan mengenai algoritma yang lebih baik dalam hal penggunaan waktu dan memori.
Kata Kunci : Su Doku, kompleksitas, Backtracking, Dancing LinksABSTRACT: Su Doku is a puzzle game popularized by the Japanese. Numbers are inserted into a 9 x 9 grid square box and the same number can’t be allowed to be laid in the same row, column or sub-box.
In this Final Assignment titled “Comparison Analysis Between Backtracking and Dancing Links Algorithms in Time and Space Domain for Su Doku Problem Solution” two algorithms were compared, thus are Backtracking and Dancing Links. Both algorithm’s complexity were calculated manually, then compared with each other for their solving capability in Su Doku. Both test then being examined to see if they support each other’s result, thus we can conclude which algorithm is better, in term of time and memory usage.
The test result shows that Dancing Links can find the solution faster, but Backtracking has a slight advantage in term of memory usage.
Keyword: Su Doku, complexity, Backtracking, Dancing Links