ALGORITMA GREEDY GRAPH COLORING UNTUK MENYELESAIKAN PERMAINAN SUDOKU

71110081, ARMA HENDRIANTA (2017) ALGORITMA GREEDY GRAPH COLORING UNTUK MENYELESAIKAN PERMAINAN SUDOKU. Final Year Projects (S1) thesis, Universitas Kristen Duta Wacana.

	Text (Skripsi Informatika) 71110081_bab1_bab5_daftarpustaka.pdf Download (6MB)
	Text (Skripsi Informatika) 71110081_bab2-sd-bab4_lampiran.pdf Restricted to Registered users only Download (48MB) | Request a copy

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.

Actions (login required)

View Item