Penyelesaian permainan masyu (pearl puzzle) dengan algoritma ketetanggaan dan Depth-First Search (DFS)

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.