PENGEMBANGAN PROTOTIPE SUDOKU SOLVER BERBASIS SISTEM MULTI AGEN

Abstrak

Sudoku adalah sejenis teka-teki logika yang tujuan akhirnya adalah mengisikan angka-angka 1 sampai dengan 9 ke dalam suatu kotak berukuran 9x9. Kotak ini memiliki 9 sub-kotak berukuran 3x3. Syarat teka-teki ini adalah tidak ada angka yang berulang pada setiap baris, kolom, atau sub-kotak. Teka-teki Sudoku termasuk ke dalam permasalahan kombinatorial (NP complete). Solusi untuk teka-teki ini dapat dicari dengan bermacam-macam cara seperti algoritma genetik, heuristik, dan sebagainya.
Penelitian ini merupakan penelitian lanjutan dari penelitian sebelumnya yang berjudul “Pemodelan Permainan Sudoku sebagai Block-World Problem” yang telah menghasilkan tiga model untuk Sudoku solver. Pada penelitian tersebut Block-World Problem dipandang sebagai sistem multi agen berparameter. Model ditulis secara formal dengan notasi TLA+.
Pada penelitian ini diusulkan satu model baru yang merupakan varian dari model yang sudah ada. Penelitian ini juga menghasilkan sebuah framework Sudoku Solver yaitu program yang dapat digunakan untuk membangun sebuah solver berdasarkan model tertentu. Dengan framework tersebut dikembangkan prototype Sudoku solver berdasarkan model yang telah dihasilkan. Keempat model yang telah diusulkan telah diimplementasikan pada framework tersebut. Eksperimen terhadap kinerja dari seluruh solver dilakukan dengan melihat keberhasilannya dalam mencari solusi untuk sekumpulan soal Sudoku dilihat dari sisi waktu dan banyaknya permainan yang dapat diselesaikan.