Perbandingan algoritma backtracking dengan algoritma hybrid genetic untuk menyelesaikan permainan calcudoku

Abstract

Calcudoku adalah sebuah permainan teka-teki angka. Tujuan dari teka-teki ini adalah mengisi setiap sel dalam grid dengan angka 1 sampai n tanpa pengulangan angka dalam setiap kolomnya dan barisnya untuk grid berukuran n × n. Grid ini dibagi menjadi sejumlah cage dengan setiap cage yang jumlah selnya bervariasi. Setiap cage dibatasi oleh garis yang lebih tebal daripada garis pembatas antar sel. Angka-angka dalam satu cage yang sama harus menghasilkan angka tujuan yang telah ditentukan jika dihitung menggunakan operasi matematika yang ditentukan. Angka-angka dalam satu cage juga boleh berulang, selama pengulangan tidak terjadi dalam satu kolom atau baris yang sama.

Dua algoritma telah terbukti berhasil dalam menyelesaikan Calcudoku, yaitu algoritma backtracking dan algoritma hybrid genetic.

Algoritma backtracking adalah sebuah algoritma umum yang mencari solusi dengan mencoba salah satu dari beberapa pilihan, jika pilihan yang dipilih ternyata salah, komputasi dimulai lagi pada titik pilihan dan mencoba pilihan lainnya.

Algoritma hybrid genetic dalam kasus ini adalah gabungan dari algoritma rule based dan algoritma genetik. Algoritma rule based adalah sebuah algoritma berbasis aturan logika untuk menyelesaikan Calcudoku. Algoritma genetik adalah salah satu teknik heuristik Generate and Test yang terinspirasi oleh sistem seleksi alam yang mencari solusi dengan menggunakan operator-operator genetik seperti mutasi, kawin silang, dan elitism.

Perangkat lunak algoritma backtracking dapat menyelesaikan semua permainan yang diujikan. Tetapi pada ukuran grid yang besar, algoritma backtracking sangat lambat dalam menyelesaikan permainan. Ada kemungkinan algoritma hybrid genetic gagal dalam menyelesaikan permainan karena sifat acak dari algoritma hybrid genetic ini. Semakin besar ukuran grid, maka kemungkinan algoritma hybrid genetic gagal dalam menyelesaikan permainan semakin besar. Pada ukuran grid yang kecil, algoritma hybrid genetic cenderung menyelesaikan permainan lebih lambat daripada algoritma backtracking. Tetapi pada ukuran grid yang besar, algoritma hybrid genetic gagal dalam menyelesaikan permainan, sehingga performansinya tidak bisa dibandingkan dengan algoritma backtracking. Banyaknya sel yang diisi pada tahap algoritma rule based dan nilai untuk parameter-parameter algoritma genetik mempengaruhi kecepatan dan tingkat keberhasilan algoritma hybrid genetic dalam menyelesaikan permainan.