Penyelesaian Teka Teki Silang dengan CSP (Constraint Satisfaction Problem) menggunakan Algoritma Backtracking

          Pada kali ini kita akan mencoba menyelesaikan Teka Teki Silang dengan menggunakan Algoritma Backtracking. Algoritma Backtracking adalah algoritma yang berbasis pada DFS (Depth First Search) untuk mencari solusi persoalan secara lebih efisien, merupakan perbaikan dari algoritma  brute-force, secara sistematis mencari solusi persoalan diantara semua kemungkinan solusi yang ada. Dengan Algoritma Backtracking kita tidak perlu memeriksa semua kemingkinan solusi yang ada. Hanya pencarian yang mengarah ke solusi saja yang perlu dipertimbangkan. Akibatnya, waktu pencarian dapat dihemat.

Untuk menyelesaika masalah teka teki silang yaitu dengan cara di kaitkan dari kalimat pada teka-teki silang dengan jawaban yang cocok. Pada teka-teki silang telah di sediakan pilihan kata jawabanya.

Mendatar                                        Menurun

1. Cukai                                                               1. Alat Transportasi Umum

3. Tidak Benar                                                     2. Memperbolehkan (B.Ing)

5. Pramuria                                                          3. Jenis Kertas

Pilihan kata : BEA, WTS, ALLOW, SALAH, HVS, BUS

Lakukan pengelompokan pilihan kata berdasarkan isi kotak (domain). Sel merupakan bayaknya node/kotak yang akan di isi.

Pada Kotak TTS diketahui bahwa Syarat :

Huruf ke-1 kotak 1 mendatar= huruf ke-1 kotak 1 Menurun

Huruf ke-3 kotak 1 mendatar= huruf ke-1 kotak 2 Menurun

Huruf ke-3 kotak 1 menurun = huruf ke-1 kotak 3 Mendatar

Huruf ke-3 kotak 1 mendatar= huruf ke-1 kotak 2 Menurun

Huruf ke-5 kotak 2 mendatar= huruf ke-1 kotak 5 Medatar

Huruf ke-5 kotak 3 mendatar= huruf ke-1 kotak 4 Menurun

Huruf ke-3 kotak 5 mendatar= huruf ke-3 kotak 4 Menurun

TTS akan Diselesaikan dengan Backtracking. Urutan pada memasukan kata adalah : 

1 Datar, 1 Turun, 3 Datar, 2 Turun, 4 Turun, 5 Datar

Constraint Satisfaction Problem terdiri dari 3 komponen:

• Set Variabel = Kotak kosong
• Set Domain = Pertanyaan dan kata-kata yang disediakan
• Set Constraint/Batasan = Salah satu huruf pada kata-kata menurun/mendatar harus sesuai dengan salah satu huruf pada kata-kata menurun/mendatar lainnya

Definisi Problem 4 Items :

1. Initial State : 
   
2. Successor Fungtion : Kata-kata yang diisi dari mulai nomor 1 mendatar/menurun, nomor 2, nomor 3 dan seterusnya hingga semua kotak terisi penuh dengan huruf yang menjadi sebuah kata.
3. Path Cost : Menurut berapa banyak kotak yang tersedia pada Teka Teki Silang tersebut.
4. Goal State : 
   

Sumber Referensi :

https://www.academia.edu/19767265/Penggunaan_Algoritma_Backtracking_pada_Penyelesaian_Teka-Teki_Silang