Sudoku dengan Pemrograman Linear Integer

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.