Algoritma Backtracking (Runut-Balik) Dalam Pengisian Teka-Teki Silang (TTS)

Algoritma Backtracking (Runut-Balik) Dalam Pengisian Teka-Teki Silang (TTS)

Algoritma runut balik pertama kali diperkenalkan oleh D.H. Lehmer pada tahun 1950. Algoritma ini cukup praktis untuk digunakan dalam beberapa penyelesaian masalah dan juga untuk memberikan kecerdasaan buatan dalam game. Beberapa game populer seperti: Sudoku, Labirin, Catur juga bisa diimplementasikan dengan menggunakan algoritma runut balik. Algoritma runut balik (back tracking) merupakan algoritma yang digunakan untuk mencari solusi persoalan secara lebih praktis daripada menggunakan algoritma brute force. Algoritma ini akan mencari solusi berdasarkan ruang solusi yang ada secara sistematis namun tidak semua ruang solusi akan diperiksa, hanya pencarian yang mengarah kepada solusi yang akan diproses.

Algoritma Runut Balik berbasis pada DFS (Depth First Search) sehingga aturan pencariannya akan mengikut kepada aturan pencarian DFS yaitu dengan mencari solusi dari akar ke daun (dalam pohon ruang solusi) dengan pencarian kedalam. Simpul-simpul yang sudah dilahirkan (diperiksa) dinamakan sipmup hidup (live node). Simpul hidup yang sedang diperluas dinamakan simpul-E atau Expand Node.

Algoritma runut balik memiliki property umum yaitu :

1)         Solusi persoalan

 Solusi dinyatakan sebagai vektor dengan n-tuple:

X = (x1, x2, …, xn), xi ∈ Si .

Mungkin saja S1 = S2 = … = Sn.

Contoh: Si = {0, 1}, xi = 0 atau 1

2)        Fungsi pembangkit nilai xk

Dinyatakan sebagai:

T(k)

T(k) membangkitkan nilai untuk xk, yang merupakan komponen vektor solusi.

3)        Fungsi pembatas (pada beberapa persoalan fungsi ini dinamakan fungsi kriteria)

Dinyatakan sebagai B(x1, x2, …, xk)

B bernilai true jika (x1, x2, …, xk) mengarah ke solusi.

Jika true, maka pembangkitan nilai untuk xk+1 dilanjutkan, tetapi jika

false, maka (x1, x2, …, xk) dibuang dan tidak dipertimbangkan lagi

dalam pencarian solusi.

Solusi persoalan adalah kemungkinan solusi yang didapatkan dari permasalahan yang diberikan, sedangakan fungsi pembatas merupakan fungsi yang akan menentukan langkah selanjutnya berupa penerusan pencarian solusi ataupun melakukan backtrack.

                                     

 Gambar 1. Papan Permainan TTS

Penerapan Algoritma Runut Balik dalam permainan Teka-Teki Silang

          Dalam penyelesaian kasus pembuatan soal teka-teki silang ini dapat diterapkan algoritma brute force. Algoritma Brute force adalah sebuah pendekatan yang lurus (straightforward) untuk memecahkan suatu masalah, biasanya didasarkan pada pernyataan masalah (problem statement) dan definisi konsep yang dilibatkan. Namun sayangnya hal ini tidak efisien karena semua kemungkinan akan dicoba. Sebagai contoh : Jika terdapat n buah kata dalam data base kata dan terdapat m jumlah deretan koak yang harus diisi maka jumlah proses untuk setiap deretan kata, harus dicoba sebanyak n! dari keseluruhan katadidalam data base, sehingga jumlah proses yang diperlukan adalah m x n ! dan kompleksitas algoritmanya menjadi 0(mn!).

Karena itulah diperlukan algoritma lain yang lebih efisien, dalam hal ini salah satunya adalah algoritma runut balik. Algoritma runut balik dalam permainan ini akan digunakan untuk mengisi kotak-kotak permainan yang sebelumnya telah dibuat. Kotak-kotak ini biasa direpresentasikan dengan struktur data matriks sehingga setiap kotak akan memiliki indeks. Indeks ini akan digunakan untuk melakukan pencarian kata yang cocok pada pengisian kata kedalam kotak-kotak, pertama-tama program akan menentukan deretan kotak awal yang ingin diisi. Program akan menghitung jumlah kotak pada deretan kotak tersebut kemudian akan mencari kata (didalam data base yang terdiri atas kumpulan kata (jawaban) yang memiliki jumlah karakter sama dengan jumlah kotak tersebut.

Dalam pencarian data kata-kata mungkin akan terdapat beberapa kata yang cocok untuk dimasukkan kedalam satu deretan kotak, untuk itu program akan memilih kata yang berada lebih awal dalam data base kata. Langkah selanjutnya, program akan mengidentifikasi indeks pada deretan kotak yang terhubung dengan deretan kotak lainnya. Program akan mencatat dimana letak hubungan antar deretan kotak tersebut kemudian mencatat indeks dan mengambil karakter yang terdapat di dalamnya untuk dibandingkan kembali dengan deretan kata yang ada di dalam data base kata. Jika kata yang dimasukkan berikutnya cocok maka pencarian akan dilanjutkan, namun jika tidak terdapat kata yang cocok maka program akan mematikan kemungkinan jawaban berdasarkan pencarian tersebut dan program akan melakukan backtrack. Backtrack dilakukan dengan cara program akan menghapus kata yang terakhir dimasukkan kedalam deretan kotak, kemudian program akan mengganti kata tersebut dengan kata lain yang juga bisa diisikan kedalam deretan kotak tersebut dan kemudian program akan melakukan pencarian ulang. Langkah-langkah diatas akan terus dilakukan secara rekursif, sampai program menemukan solusi dari permasalahan (seluruh kotak terisi) atau program tidak menemukan solusi (tidak ada kemungkinan jawaban yang valid).

             Contoh listing program pada sebuah teka-teki silang :