Teka-teki SUDOKU 9 X9 memiliki aturan sebagai berikut. Setiap baris dan kolom harus mempunyai angka antara 1 dan 9 dan setiap kotak bagian dalam harus mempunyai angka antara 1 dan 9. Setiap angka dalam setiap kolom dan baris dan dalam setiap kotak kecil hanya boleh muncul satu kali.
Mari kita definisikan Xijk untuk semua nilai I, j dan k dari 1 sampai 9 menjadi 1. Jika sel (I,j) berisi angka k dimana I, j dan k semuanya berkisar antara 1 dan 9. Di sini saya menyatakan baris ke-i dan j menandakan kolom ke-j dan k menandakan bilangan bulat antara 1 dan 9. Jika X134 = 1, berarti sel (1,3) berisi angka 4. Hal ini juga berarti bahwa tidak ada elemen lain dari baris ke-1 atau kolom ke-3 kecuali sel (1,3) boleh sama dengan 4.
Untuk memodelkan SUDOKU kita akan menggunakan total 729 variabel.
Sekarang mari kita rumuskan secara aljabar masing-masing dari ketiga kelas aturan tersebut.
Setiap baris harus berisi angka antara 1 dan 9 tepat satu kali saja.
Untuk baris pertama, aturan ini akan muncul sebagai (diistilahkan sebagai “Kendala” Dalam bahasa Pemrograman Integer).
untuk setiap I dari 1 hingga 9 dan untuk setiap k dari 1 hingga 9 (I adalah representasi matematis dari variabel penghitung)
jumlah (Xijk) untuk semua j dari 1 sampai 9 = 1;
Ditulis dalam bentuk verbose untuk baris ke-1 setiap angka antara 1 sampai 9
X111 + X121 + X131 + X141 + X151 + X161 + X171 + X181 + X191 = 1.
X112 + X122 + X132 + X142 + X152 + X162 + X172 + X182 + X192 = 1.
X113 + X123 + X133 + X143 + X153 + X163 + X173 + X183 + X193 = 1.
X114 + X124 + X134 + X144 + X154 + X164 + X174 + X184 + X194 = 1.
Persamaan ini berlaku untuk variabel yang dimulai dengan X115 hingga X119.
Mari kita rumuskan persamaan aturan setiap bilangan antara 1 dan 9 yang hanya muncul satu kali dalam masing-masing 9 kolom.
Ditulis dalam notasi matematika,
jumlah X untuk setiap j dari 1 sampai 9 (untuk semua I dan k antara 1 sampai 9) = 1
Ditulis dalam bentuk verbose untuk beberapa kolom setiap angka antara 1 sampai 9
Kolom 1
X111 + X211 + X311 + X411 + X511 + X611 + X711 + X811 + X911 = 1.
X112 + X212 + X312 + X412 + X512 + X612 + X712 + X812 + X912 = 1.
X113 + X213 + X313 + X413 + X513 + X613 + X713 + X813 + X913 = 1.
Ini harus diisi untuk semua nomor lainnya 4 sampai 9.
Kolom 2
X121 + X221 + X321 + X421 + X521 + X621 + X721 + X821 + X921 = 1.
X122 + X222 + X322 + X422 + X522 + X622 + X722 + X822 + X922 = 1.
X123 + X223 + X323 + X423 + X523 + X623 + X723 + X823 + X923 = 1.
Ini harus diisi untuk semua nomor lainnya dari 4 sampai 9.
Sekarang mari kita nyatakan kotak-kotak kecil (3 x 3) yang berjumlah 9 kotak.
Jadi dalam setiap kotak berukuran 3 x 3, harus ada hanya satu 1 atau 2 atau 3 atau 4 atau 5 atau 6 atau 7 atau 8 atau 9 dst.,
Sel berada di antara Kolom (1 hingga 3) dan Baris (1 hingga 3), Kolom (4 hingga 6) dan Baris (1 hingga 3) Kolom (7 hingga 9) baris (1 hingga 3). Juga untuk kumpulan kolom yang sama, mereka muncul dalam baris (4 hingga 6) dan (6 hingga 9). Jadi mari kita rumuskan persamaan hanya untuk satu persegi kecil yang terletak di antara kolom (1 sampai 3) dan baris (1 sampai 3). Variabel keputusan yang sesuai untuk digit “1” adalah (total 9)
X111, X121, X131, X211,X221,X231,X311, X321,X331.
Mari kita rumuskan persamaan bahwa persegi (3 x3) ini hanya menampung satu “1”.
Jadi persamaannya adalah
X111 + X121+ X131 + X211 +X221+ X231+ X311 + X321 + X331 = 1.
Persamaan di atas menyiratkan bahwa hanya satu dari 9 variabel ini atau hanya satu dari sembilan sel ini yang dapat mengambil nilai 1.
Demikian pula kendala harus dirumuskan untuk angka “2”, angka “3” dan seterusnya sampai angka 9.
Untuk permasalahan pemrograman bilangan bulat, selain persamaan yang menjelaskan batasannya, juga harus ada batasan bilangan bulat yang dikenakan pada setiap variabel sehingga pada akhirnya ketika sistem persamaan diselesaikan, kita mendapatkan 0 atau 1 sebagai solusi untuk variabel Xijk. .
Persamaan geometri dari masalah program linier dengan fungsi tujuan dan beberapa batasan tidak lain adalah sebuah polihedron berdimensi dimana n mewakili jumlah batasan dalam masalah tersebut. Biasanya solusi optimal akan ditemukan pada simpul-simpul politop, juga aturan beberapa metode seperti SIMPLEX akan mengharuskan politop berbentuk cembung sehingga seseorang dapat melintasi dari simpul ke simpul di sepanjang tepinya dan menemukan solusi optimal.
Menerapkan batasan bilangan bulat sebagai tambahan berarti bahwa solusi optimal tidak akan berada pada simpul politop karena solusi yang ditemukan pada simpul tersebut mungkin bukan bilangan bulat. Jadi setelah memperhitungkan bahwa solusi optimal harus 0 atau 1 berarti secara geometris solusi tersebut akan berada di suatu tempat di dalam daerah layak politop cembung dan pada salah satu dari banyak garis lurus yang berasal dari bidang hiper yang setara dengan Xi jk yang mempunyai bilangan bulat. nilai-nilai.
Perlu diperhatikan bahwa solusi di atas telah menggunakan 729 variabel keputusan dan 81 baris batasan. 81 batasan kolom dan 729 batasan persegi kecil dengan total 901 batasan. Fungsi tujuan bisa banyak, tetapi fungsi tujuan dapat dirumuskan sebagai mencari nilai min (jumlah seluruh 729 variabel). Seseorang dapat mengurangi jumlah kendala dengan menemukan beberapa redundansi.
Persamaan di atas tidak dapat diselesaikan dengan menggunakan bahasa pemrograman seperti Visual Basic, Pascal atau C. Permasalahan pemrograman integer dapat diselesaikan dengan menggunakan software optimasi seperti CPLEX optimizer, add-on Excel untuk menyelesaikan masalah Linear Programming, Lingo dll.