Memecahkan SUDOKU dengan Binary Integer Linear Programming (BILP) – Menuju AI

Memecahkan SUDOKU dengan Binary Integer Linear Programming (BILP) – Menuju AI

Pengarang: Harjot Kauro

Awalnya diterbitkan di Towards AI the World’s Leading AI and Technology News and Media Company. Jika Anda sedang membangun produk atau layanan terkait AI, kami mengundang Anda untuk mempertimbangkan untuk menjadi sponsor AI. Di Towards AI, kami membantu menskalakan AI dan startup teknologi. Biarkan kami membantu Anda melepaskan teknologi Anda kepada massa.

SUDOKU dengan Binary Integer Linear Programming (BILP)

Latar belakang

Sudoku adalah teka-teki berbasis logika yang pertama kali muncul di AS dengan judul “Tempat Nomor” pada tahun 1979 di majalah Dell Pencil Puzzles & Word Games [6]. Permainan ini dirancang oleh Howard Garns, seorang arsitek yang, setelah pensiun, beralih ke pembuatan teka-teki. Pada 1980-an, permainan ini semakin populer di Jepang dan dinamai ulang oleh penerbit Nikoli menjadi “suji wa dokushin ni kagiru,” yang diterjemahkan sebagai “angka harus tetap tunggal.” Ini akhirnya disingkat menjadi “sudoku” atau “nomor tunggal.”

Perhatian — dengan asumsi pembaca sudah mengetahui dasar-dasar Pemrograman Linier

Apakah Sudoku merupakan masalah pengoptimalan?

Tidak. Sebagian besar tidak. Karena tidak ada fungsi tujuan yang ingin kita maksimalkan atau minimalkan. Masalah sudoku bisa disebut masalah satisfiability atau feasibility.

Mari kita mulai dengan aturan…

Sudoku paling sering muncul dalam bentuk matriks 9 × 9. Aturannya sederhana: isi matriks sehingga setiap baris, kolom, dan submatriks 3 × 3 berisi angka 1 sampai 9 tepat satu kali. Setiap teka-teki muncul dengan jumlah tertentu yang diberikan. Jumlah dan lokasi ini menentukan tingkat kesulitan permainan.

Seperti yang kita ketahui, setiap masalah ILP terdiri dari fungsi tujuan (tidak berlaku dalam kasus Sudoku kecuali ada solusi alternatif), variabel keputusan, dan kendala.

Kabar baiknya adalah kita tidak menulis batasan untuk ini, kita hanya secara matematis memasang aturan teka-teki sebagai batasan!

Model matematika Pemrograman Integer dari teka-teki Sudoku

Untuk memudahkan penjelasan, saya akan menggunakan matriks 4×4 di depan. Mari kita perhatikan teka-teki berikut untuk diselesaikan dengan menggunakan BILP.

Gambar 1: Teka-teki sudoku 4×4

Lebih khusus lagi, kita akan merumuskan program bilangan bulat biner (BILP) untuk teka-teki nxn umum. Setelah program dikembangkan untuk memecahkan BILP untuk Gambar 1, program dapat dengan mudah diadaptasi untuk memecahkan teka-teki Sudoku.

Untuk memulai, kami mendefinisikan variabel keputusan kami:

Variabel Keputusan Biner Umum

Ketika nilai dari variabel keputusan ditentukan, kita akan mengetahui apakah setiap bilangan bulat k(1 k≤4) muncul di setiap elemen (i,j) dari matriks Sudoku n×n. Artinya, solusi untuk teka-teki Sudoku yang sesuai akan ditentukan.

Kami sekarang beralih ke fungsi tujuan yang selalu penting dan serangkaian kendala. Perhatikan bagaimana kendala hanya memerlukan pengetahuan tentang aturan teka-teki Sudoku (dengan penambahan satu kendala implisit, yang merupakan kendala (6) di bawah) dan tidak memerlukan kemahiran dengan logika yang diperlukan untuk memecahkan teka-teki tersebut dengan tangan. Formulasi BILP yang cocok untuk teka-teki Sudoku adalah sebagai berikut:

Min 0 (mari kita definisikan ini sebagai konstanta, karena tidak ada fungsi untuk meminimalkan atau memaksimalkan)

Tunduk pada

Batasan 1: Setiap sel berisi satu bilangan bulat k

Batasan 2: Setiap bilangan bulat k muncul sekali di setiap baris

Batasan 3: Setiap bilangan bulat k muncul sekali di setiap kolom

Batasan 4: Setiap bilangan bulat k muncul satu kali di setiap submatriks

Batasan 5: Elemen yang diberikan G dalam matriks diatur “on”

Batasan 6: Mendefinisikan kemungkinan nilai bilangan bulat

Dan, itu saja!

Mari selesaikan teka-teki Sudoku 4×4 di atas (Gambar 1) menggunakan Excel Solver. Template simulasi untuk teka-teki 4×4 dengan 64 variabel keputusan biner akan terlihat seperti ini.

Template Simulasi Sudoku dengan 64 Variabel Keputusan Biner

Sekarang, mari kita tafsirkan batasan-batasan yang disebutkan di atas:

Batasan 1: Setiap sel berisi satu bilangan bulat k. Tab berwarna hijau(Jumlah i,j = 1) akan memastikan bahwa setiap posisi diisi dengan nilai integer.

Batasan 2: Setiap bilangan bulat k muncul satu kali dalam setiap baris. Tab berwarna merah bata (Jumlah baris 1:4 >= 1) akan memastikan bahwa setiap k muncul hanya sekali di setiap baris.

Batasan 3: Setiap bilangan bulat k muncul satu kali di setiap kolom. Tab berwarna zaitun (Jumlah kolom 1:16 >= 1) akan memastikan bahwa setiap k muncul hanya sekali di setiap kolom.

Batasan 4: Setiap bilangan bulat k muncul satu kali dalam setiap submatriks. Tab berwarna pirus(Jumlah kuadran 1:4 >= 1) akan memastikan bahwa setiap k muncul hanya sekali dalam setiap matriks 2×2.

Batasan 5: Diberikan elemen G dalam matriks diatur “on”. Nilai k yang diberikan adalah kode keras.

Langkah terakhir adalah mengonversi solusi Program Integer seperti yang diberikan dalam 64 sel variabel keputusan kuning, persik, abu-abu, dan biru ke kisi Sudoku 4 kali 4 yang diperlukan. Setiap sel biner kemudian dikalikan dengan kemungkinan set nilai yang dapat diambil oleh “k” (yaitu {1,2,3,4}).

Sekarang mari kita cari solusinya…

Beginilah tampilan Excel Solver

Pemecah Excel

…dan Voila! Solusi untuk teka-teki 4×4 akan terlihat seperti ini.

Solusi untuk teka-teki pada Gambar1

Kata-kata terakhir

Logika di atas dapat digunakan tidak hanya untuk memecahkan teka-teki Sudoku tetapi juga untuk membuatnya. Saya harap, Anda juga merasa mudah untuk memahami dan menyenangkan! Terhubung dengan saya di Linkedin untuk berbicara lebih banyak tentang pengoptimalan.

Memecahkan SUDOKU dengan Binary Integer Linear Programming (BILP) awalnya diterbitkan di Towards AI on Medium, di mana orang-orang melanjutkan percakapan dengan menyoroti dan menanggapi cerita ini.

Diterbitkan melalui Menuju AI

Author: Scott Anderson