ALGORITMA GREEDY GRAPH COLORING UNTUK MENYELESAIKAN PERMAINAN SUDOKU

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

[img] Text (Skripsi Informatika)
71110081_bab1_bab5_daftarpustaka.pdf

Download (6MB)
[img] 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.

Item Type: Thesis (Bachelor)
Uncontrolled Keywords: Sudoku, Greedy Graph Coloring, Graph Theory, Algoritma Graf
Subjects: Q Science > QA Mathematics
Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Q Science > QA Mathematics > QA76 Computer software
Divisions: Fakultas Teknologi Informasi > Prodi Informatika
Depositing User: ms maria sema
Date Deposited: 28 Aug 2020 07:35
Last Modified: 28 Aug 2020 07:35
URI: http://katalog.ukdw.ac.id/id/eprint/1653

Actions (login required)

View Item View Item