Abstract:
Hitori adalah sebuah permainan puzzle yang dimainkan pada bidang dua dimensi dengan ukuran
baris dan kolom yang sama. Permainan ini diterbitkan oleh sebuah perusahaan penerbit asal
Tokyo, Jepang. Permainan Hitori diperkenalkan pertama kali ke publik pada Maret 1990. Hitori
dimainkan dengan mengeliminasi angka-angka dengan kemunculan lebih dari satu kali, yang
terdapat pada baris maupun kolom bidang permainan. Angka-angka yang dieliminasi pun
tidak boleh saling bertetangga satu sama lain, baik secara horizontal maupun vertikal (bidang
orthogonal). Kemudian angka-angka yang tidak dieliminasi harus saling terhubung satu sama lain
dan tidak terisolasi oleh angka-angka yang dieliminasi. Permainan Hitori berhasil diselesaikan
apabila tidak terdapat angka-angka duplikat pada tiap baris dan tiap kolom permainan. Hitori
merupakan permainan logika yang bersifat NP-Complete, dimana solusi dari permainan ini dapat
dicari dengan menggunakan algoritma Brute Force.
Algoritma genetika merupakan algoritma pencarian yang terinspirasi dari proses natural
selection. Algoritma genetika dapat digunakan untuk memecahkan combinatorial optimization
problems yang sulit. Algoritma genetika ini dikemukakan oleh John Holland dari Michigan
University pada 1975. John Holland mengkombinasikan keberhasilan suatu struktur untuk
bertahan hidup (survival of the fittest).
Algoritma genetika menjalankan operasi-operasi seleksi, persilangan, mutasi, dan elitism
untuk mencari kandidat solusi dari suatu permasalahan yang hendak diselesaikan. Aturan-aturan
main pada permainan Hitori akan dijadikan sebagai landasan penghitungan nilai fitness pada
algoritma genetika yang akan diimplementasikan. Singkatnya, semakin banyak aturan main yang
dilanggar oleh sebuah kandidat solusi, maka nilai fitness untuk kandidat solusi tersebut semakin
buruk/kecil. Kandidat solusi yang tidak melanggar satu pun aturan main dari permainan
Hitori, ditampilkan sebagai solusi dari permainan Hitori. Pada penelitian ini dibangun sebuah
perangkat lunak permainan puzzle Hitori dengan ukuran 5x5, algoritma genetika diterapkan
pada perangkat lunak ini untuk mencari solusi permainan dari puzzle Hitori. Hasil pengujian
atas pengimplementasian algoritma genetika dalam menyelesaikan permainan Hitori adalah
sebesar 94%. Dalam penelitian ini, algoritma genetika berhasil menyelesaikan 47 soal permainan
Hitori dari 50 soal permainan yang tersedia.