Abstract:
Permainan teka-teki silang merupakan permainan kata yang sudah populer di seluruh dunia. Permainan ini dimainkan untuk mengisi waktu luang dan meningkatkan daya berpikir. Selain digunakan sebagai media rekreasi, permainan teka-teki silang pun dapat digunakan pada bidang pendidikan sebagai variasi soal latihan, ulangan, bahkan ujian. Tahap membangkitkan permainan teka-teki silang dinilai melelahkan dan merupakan kegiatan yang kompleks bagi manusia. Digunakan bantuan komputer untuk membangkitkan permainan teka-teki silang yang dinilai mampu membantu proses pembangkitan menjadi lebih cepat dan mudah.
Proses pembangkitan permainan teka-teki silang dapat dipandang sebagai sebuah search problem. Dengan konsep pencarian, dilakukan percobaan dalam membangkitkan teka-teki silang pada beberapa pendekatan. Terdapat pendekatan exhaustive search yang menghasilkan kasus uji yang dinilai buruk, pendekatan dengan pencarian lokal particle swarm optimization yang dinilai menghasilkan fungsi fitness baik pada hasil namun sulit pada tahap pemodelan, dan pendekatan pencarian lokal hill climbing random-restart yang menjadi dasar pendekatan perangkat lunak dibangun pada penelitian ini. Dengan pendekatan hill climbing random-restart, perangkat lunak dibangun, diuji kebenaran fungsionalnya, dan dilakukan eksperimen untuk mendapatkan nilai parameter yang baik sehingga menghasilkan output berupa papan permainan teka-teki silang dengan fungsi fitness yang baik.
Hasil eksperimen menunjukkan bahwa parameter-parameter seperti jumlah input kata, jumlah titik start, jumlah iterasi, dan besarnya papan permainan yang dibangkitkan dapat mempengaruhi nilai fungsi fitness dan waktu komputasi. Hasil keluaran perangkat lunak akan mencapai suatu local maxima, karena pendekatan yang digunakan dalam membangkitkan papan teka-teki silang adalah hill climbing random-restart. Walaupun dipandang sebagai local maxima, output perangkat lunak sudah menyerupai permainan teka-teki silang pada umumnya yang mana ditemukan banyak kata yang berpotongan dengan kata lain.
