Abstract:
Masyu merupakan salah satu puzzle yang diterbitkan oleh Nikoli Co.Ltd. Nikoli Co.Ltd. Masyu
atau Pearl Puzzle merupakan sebuah permainan puzzle yang dimainkan dalam sebuah papan
yang berbentuk persegi atau persegi panjang, beberapa persegi di dalam papan permainan
akan diisi dengan lingkaran; setiap lingkaran yang ada memiliki warna antara “putih” (kosong)
atau “hitam” (terisi). Tujuan dari permainan Masyu adalah untuk membuat satu garis tidak
berpotongan dan melewati semua lingkran.
Pada skripsi ini akan dibuat sebuah perangkat lunak untuk penyelesaian permainan Masyu
yang berbasis web. Perangkat lunak yang dibuat merupakan pencari solusi atau solver permainan
Masyu. Perangkat lunak akan dibuat dengan bantuan React.js. React (React.js atau ReactJS)
adalah open-source, front-end, JavaScript library untuk membangun antarmuka pengguna
atau komponen UI. Dari berbagai macam teknik yang dapat digunakan untuk menyelesaikan
permainan Masyu, dipilih algoritma ketetanggaan dan DFS(Depth-first search).
Algoritma ketetanggaan titik adalah algoritma untuk mendapatkan nilai suatu titik yang
melibatkan nilai titik-titik tetangganya dan DFS(Depth-first search) adalah metode pencarian
yang dimulai dengan node awal grafik dan kemudian berjalan lebih dalam dan lebih dalam hingga
menemukan node yang diperlukan atau node yang tidak memiliki anak. Algoritma ketetanggaan
dapat memberikan solusi untuk permainan Masyu tanpa bantuan DFS(Depth-first search)
untuk soal soal tertentu, namun jika belum ditemukan solusi maka akan dilanjutkan oleh DFS.
Algoritma ketetanggaan akan berperan sebagai initial state dalam proses pencarian DFS(Depthfirst
search) yang akan menelusuri seluruh kemungkinan, sehingga solusi dari permainan Masyu
akan lebih cepat ditemukan karena kondisi awal pencarian tidak kosong.
Hasil evaluasi dari perangkat lunak adalah permainan Masyu dengan algoritma ketetanggaan
dapat digunakan untuk menyelesaikan beberapa permainan Masyu tanpa bantuan DFS.
Pemakaian algoritma ketetanggaan dan DFS pada permainan Masyu untuk ukuran papan 6 × 6,
8 × 8, dan 10 × 10 memiliki persentase pemakaian yang hampir sama, dan jumlah titik pada
permainan Masyu, jika semakin banyak belum tentu akan mempercepat waktu pencarian solusi
pada permaianan Masyu.
