ALGORITMA GREEDY GRAPH COLORING UNTUK MENYELESAIKAN PERMAINAN SUDOKU
Total View This Week0
Total View This Week0
Institusion
Universitas Kristen Duta Wacana
Author
71110081, ARMA HENDRIANTA
Subject
QA Mathematics
Datestamp
2020-08-28 07:35:02
Abstract :
Sudoku merupakan sebuah board game yang sangat populer. Terdapat banyak jenis Sudoku, yang paling dikenal, yaitu plain Sudoku 9×9. Aturan permainan ini sangat sederhana. Seorang pemain hanya perlu mengisikan angka di antara 1 sampai 9 pada cell-cell yang kosong, dengan syarat tidak boleh ada angka yang sama dalam satu baris, kolom atau subgrid. Dari aturan permainan tersebut, Sudoku dapat dilihat sebagai permasalahan pewarnaan graf. Cell merupakan verteks, angka 1 sampai 9 merupakan warna dan aturan penulisan angka sebagai verteks-verteks adjacent. Aturan permainan yang sederhana namun membutuhkan ketelitian ini membuat para penikmat board game sangat menyukainya. Karenanya, penulis merasa tertarik untuk melakukan penelitian tentang Sudoku dan pewarnaan graf. Di dalam disiplin ilmu graf, terdapat banyak metode yang dapat digunakan untuk menyelesaikan permasalahan pewarnaan graf, salah satunya yaitu greedy graph coloring. Metode ini akan diimplementasikan pada sistem (Sudoku Solver) dengan sedikit perubahan. Dari hasil pengujian yang dilakukan penulis, pada tiga tingkat kesulitan soal Sudoku (mudah, menengah dan sulit), masing-masing 20 soal, tiap kategori dan total 60 soal, diperoleh hasil yang baik dengan rata-rata keseluruhan tingkat keberhasilan mencapai 95%. Kegagalan penyelesaian disebabkan oleh kurangnya angka (warna) yang digunakan dalam sistem.
Sudoku merupakan sebuah board game yang sangat populer. Terdapat banyak jenis Sudoku, yang paling dikenal, yaitu plain Sudoku 9×9. Aturan permainan ini sangat sederhana. Seorang pemain hanya perlu mengisikan angka di antara 1 sampai 9 pada cell-cell yang kosong, dengan syarat tidak boleh ada angka yang sama dalam satu baris, kolom atau subgrid. Dari aturan permainan tersebut, Sudoku dapat dilihat sebagai permasalahan pewarnaan graf. Cell merupakan verteks, angka 1 sampai 9 merupakan warna dan aturan penulisan angka sebagai verteks-verteks adjacent. Aturan permainan yang sederhana namun membutuhkan ketelitian ini membuat para penikmat board game sangat menyukainya. Karenanya, penulis merasa tertarik untuk melakukan penelitian tentang Sudoku dan pewarnaan graf. Di dalam disiplin ilmu graf, terdapat banyak metode yang dapat digunakan untuk menyelesaikan permasalahan pewarnaan graf, salah satunya yaitu greedy graph coloring. Metode ini akan diimplementasikan pada sistem (Sudoku Solver) dengan sedikit perubahan. Dari hasil pengujian yang dilakukan penulis, pada tiga tingkat kesulitan soal Sudoku (mudah, menengah dan sulit), masing-masing 20 soal, tiap kategori dan total 60 soal, diperoleh hasil yang baik dengan rata-rata keseluruhan tingkat keberhasilan mencapai 95%. Kegagalan penyelesaian disebabkan oleh kurangnya angka (warna) yang digunakan dalam sistem.
Download
book
BibTex
Latex, Jabref
cloud_download
Original Resource
url resource Institution
