Home

Kamis, 29 November 2012

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

Teka Teki Silang atau disingkat  TTS adalah suatu permainan  di  mana  kita  harus mengisi ruang-ruang kosong (berbentuk  kotak putih) dengan huruf-huruf  yang membentuk sebuah kata berdasarkan petunjuk yang diberikan. Dalam permainan teka-teki silang terdapat papan permainan utama. Papan permainan sendiri terdiri atas kotak-kotak berwarna hitam dan putih.

Permainan ini memang cukup mudah untuk dimainkan, namun sayangnya untuk dapat membuat soal yang valid merupakan hal yang sulit. Perlu suatu program komputer untuk menyelesaikan permasalahan tersebut. Dalam pemecahan masalah, program komputer ini akan menggunakan algoritma backtracking (runut balik). Algoitma  runut-balik (backtracking) akan mampu memberikan hasil apakah deretan-deretan kotak jawaban   yang telah dibuat sudah cocok  dengan   deretan   jawaban   kata   yang disediakan.

Algoritma  backtracking  merupakan algoritma pencarian yang  berbasis pada DFS (Depth-First  Search) atau pencarian mendalam dengan tujuan mencari solusi permasalahan secara lebih praktis. Mekanisme penyelesaian dengan menggunakan backtracking berprinsip pada metode rekursif.

2 komentar: