Penerapan Pewarnaan Graf sebagai Metode untuk Mencari Solusi Permainan Sudoku

Abstract

Makalah ini membahas tentang Penerapan Pewarnaan Graf Sebagai Metode Untuk Mencari Solusi Permainan Sudoku. Sudoku adalah sebuah permainan teka-teki yang memasukan angka 1 sampai n ke dalam kotak sehingga tidak ada angka yang sama dalam satu kolom, baris maupun kotak persegi / grid. Sudoku dapat dipandang sebagai pewarnaan parsial dari graf. Sudoku dapat ditransformasi ke dalam graf dengan mengubah setiap elemen Sudoku menjadi verteks dan elemen yang bertetangga sebagai edge. Dengan demikian teknik pewarnaan graf dapat digunakan sebagai salah satu teknik untuk menyelesaikan permainan Sudoku. Setiap Sudoku n x n akan memiliki warna minimal sehingga memiliki polinomial kromatik dimana adalah warna minimal (bilangan kromatik) yang menunjukkan bahwa banyaknya solusi permainan Sudoku ada sebanyak .