Teka-teki SUDOKU 9 X9 memiliki aturan berikut. Setiap baris dan kolom harus memiliki angka antara 1 dan 9 dan setiap kotak bagian dalam harus memiliki angka antara 1 dan 9. Setiap angka di setiap kolom dan baris dan di setiap kotak kecil harus muncul hanya sekali.
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. Disini I menandakan baris ke-i dan j menunjukkan kolom ke-j dan k menunjukkan bilangan bulat antara 1 dan 9. Ketika X134 = 1, itu berarti sel (1,3) berisi angka 4. Ini juga menyiratkan bahwa tidak ada elemen lain dari baris ke-1 atau kolom ke-3 kecuali sel (1,3) bisa sama dengan 4.
Untuk memodelkan SUDOKU kita akan menggunakan total 729 variabel.
Mari kita sekarang secara aljabar merumuskan masing-masing dari tiga kelas aturan.
Setiap baris harus berisi angka antara 1 dan 9 tepat sekali saja.
Untuk baris pertama, aturan ini akan muncul sebagai ( disebut sebagai “Batasan” Dalam bahasa Pemrograman Integer).
untuk setiap I dari 1 sampai 9 dan untuk setiap k dari 1 sampai 9 (I adalah representasi matematis dari variabel counter)
jumlah (Xijk) untuk semua j dari 1 sampai 9 = 1;
Ditulis dalam bentuk verbose untuk baris ke-1 untuk 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 mengikuti untuk variabel yang dimulai dengan X115 hingga X119.
Serupa mari kita merumuskan persamaan untuk aturan setiap angka antara 1 dan 9 yang terjadi hanya sekali di masing-masing dari 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 beberapa kolom untuk setiap angka antara 1 dan 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 lain dari 4 hingga 9.
Mari kita sekarang mewakili kotak kecil ( 3 x 3 ) berjumlah 9 kotak.
Jadi di setiap kotak 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 terjadi antara Kolom (1 sampai 3) dan Baris (1 sampai 3), Kolom (4 sampai 6) dan Baris (1 sampai 3) Kolom (7 sampai 9) baris (1 sampai 3). Juga untuk set kolom yang sama mereka muncul di baris (4 sampai 6) dan (6 sampai 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 berisi satu “1”.
Jadi persamaannya adalah
X111 + X121+ X131 + X211 +X221+ X231+ X311 + X321 + X331 = 1.
Persamaan di atas akan 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 digit “2”, digit “3” dan seterusnya sampai 9.
Untuk masalah pemrograman bilangan bulat selain persamaan yang menjelaskan kendala, juga harus ada kendala bilangan bulat yang dikenakan pada setiap variabel sehingga pada akhirnya ketika sistem persamaan diselesaikan, diperoleh 0 atau 1 sebagai solusi untuk variabel Xijk .
Setara geometris dari masalah pemrograman linier dengan fungsi tujuan dan beberapa kendala tidak lain adalah polihedron dimensi di mana n mewakili jumlah kendala dalam masalah tersebut. Biasanya solusi optimal akan ditemukan pada simpul politop, juga aturan beberapa metode seperti SIMPLEX akan mengharuskan politop cembung sehingga seseorang dapat melintasi dari simpul ke simpul di sepanjang tepi dan menemukan solusi optimal.
Memaksakan kendala bilangan bulat sebagai tambahan akan berarti bahwa solusi optimal tidak akan berada di simpul politop karena solusi yang ditemukan di simpul mungkin bukan bilangan bulat. Jadi setelah memperhitungkan bahwa solusi optimal harus 0 atau 1 akan berarti bahwa secara geometris solusinya akan berada di suatu tempat di dalam wilayah layak politop cembung dan pada salah satu dari banyak garis lurus yang berasal dari hyperplane yang setara dengan Xi jk yang memiliki bilangan bulat nilai-nilai.
Catatan bahwa solusi di atas telah menggunakan 729 variabel keputusan dan 81 batasan baris. 81 pembatas kolom dan 729 pembatas kotak kecil dengan total 901 pembatas. Ada banyak fungsi tujuan, tetapi seseorang dapat memformulasikan fungsi tujuan sebagai mencari min dari (jumlah dari semua 729 variabel). Satu dapat mengurangi jumlah kendala dengan menemukan beberapa redundansi.
Persamaan-persamaan di atas tidak dapat diselesaikan dengan menggunakan bahasa pemrograman seperti Visual Basic, Pascal atau C. Masalah pemrograman bilangan bulat dapat diselesaikan dengan menggunakan perangkat lunak pengoptimalan seperti pengoptimal CPLEX, addin Excel untuk menyelesaikan masalah Pemrograman Linier, Lingo dll.