Abstract:
Sudoku merupakan permainan teka-teki logika yang umumnya berukuran 9 × 9. Aturan standar
dari Sudoku adalah mengisi seluruh kisi yang tersedia sebagaimana sehingga masing-masing
sel dalam setiap baris, kolom, dan subkisi beirisi satu angka dari 1 sampai 9. Selain ukuran
tersebut, teka-teki Sudoku juga dapat berukuran lain, yaitu n2 × n2 dengan n adalah integer
lebih dari satu. Untuk menyelesaikan masalah Sudoku dapat digunakan pemrograman linear
integer (ILP) dengan metode branch and bound. Pada skripsi ini, dibahas penyelesaian teka-teki
Sudoku standar 4 × 4 dan perumumannya yaitu Sudoku standar n2 × n2 dengan mengubah
aturan-aturan ke dalam model matematis. Selain penyelesaian masalah, dibahas juga cara
pembuatan masalah Sudoku standar n2 × n2 dengan solusi unik. Kemudian, diakhiri dengan
penambahan kendala pada model matematis untuk menangani variasi aturan Sudoku 9×9, yaitu
Sudoku X, Sudoku Center Dot, dan Hypersudoku. Penyelesaian permasalahan Sudoku dengan
menggunakan ILP merupakan hal yang rumit, karena diperlukan banyaknya iterasi dan variabel
yang digunakan. Oleh karena itu, seluruh pengerjaan diselesaikan dengan menggunakan bantuan
program Python. Program yang dibuat untuk menemukan solusi dari permasalahan Sudoku
standar n2 × n2, membuat permasalahan permasalahan Sudoku standar n2 × n2 dengan solusi
unik, dan menyelesaikan permasalahan variasi aturan Sudoku 9 × 9, yaitu Sudoku X, Sudoku
Center Dot, dan Hypersudoku.
