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.
Algoritma backtracking dalam permainan ini akan digunakan untuk mengisi kotak-kotak permainan yang sebelumnya telah dibuat. Kotak-kotak ini bisa direpresentasikan dengan struktur data matriks sehingga setiap kotak akan memiliki indeks. Indeks ini akan digunakan untuk melakukan pencarian kata yang cocok. Pada pengisian kata ke dalam kotak-kotak, pertama-tama program akan menentukan deretan kotak awal yang ngin diisi. Program akan menghitung jumlah kotak pada deretan kotak tersebut kemudian akan mencari kata di dalam database (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 database 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 database 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 ke dalam deretan kotak, kemudian program akan mengganti kata tersebut dengan kata lain yang juga bisa diisikan ke dalam 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).
Dalam permainan teka-teki silang ini, algoritma Backtracking sudah bisa memberikan jawaban yang pasti sehingga algoritma Backtracking ini bisa dimplementasikan. Selain itu algoritma Backtrack juga merupakan algoritma yang sederhana namun cukup praktis dibandingkan dengan algoritma brute force. Hal ini disebabkan karena pada prinsipnya, kita tidak perlu memeriksa semua kemungkinan solusi yang ada. Pencarian hanya mengarah pada solusi yang dipertimbangkan saja.
Meski demikian, algoritma backtracking masih memiliki kelemahan, yaitu hanya bisa diaplikasikan terbatas pada tipe permasalahan yang memiliki solusi yang dapat dicari secara sistematis dan bertahap. Terdapat masalah-masalah yang tidak bisa diselesaikan dengan menggunakan backtracking, misalnya menemukan suatu nilai yang diminta pada tabel yang tidak terurut. Namun ketika algoritma ini dapat diaplikasikan, backtracking dapat bekerja jauh lebih cepat dari brute force karena jumlah kandidat solusi yang dapat dibuang dengan backtracking cukup besar.
1 komentar:
terimakasih atas responnya...nanti akan saya kunjungi dan saya minta izin untuk saya share di blog ini/
Posting Komentar