Solving Sudoku using integer programming
A SUDOKU 9 X9 puzzle has the following rules. Each row and column must have the numbers between 1 and 9 and each of the inner squares must have the numbers between 1 and 9.
Let’s simply define Xijk so that all values of I, j and k from 1 to 9 are 1. If cell (I, j) contains the number k where I, j and k range from 1 to 9. Here I denotes the ith row and j denotes the j-th column and k denotes an integer between 1 and 9. When X134 = 1, it means that cell (1,3) contains the number 4. This would also imply that none of the other elements in the 1st row or 3rd column except cell (1,3) can be equal to 4.
To model the SUDOKU we will use a total of 729 variables.
Let us now algebraically formulate each of the three classes of rules.
Each row must contain a number between 1 and 9 exactly once.
For the first row, this rule would appear as (called a “Constraint” in the integer programming language).
for each I from 1 to 9 and for each k from 1 to 9 (I is a mathematical representation of a counter variable)
sum (Xijk) for all j from 1 to 9 = 1;
Written in verbose form for the first row of each number between 1 and 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.
These equations follow for variables beginning with X115 through X119.
Similarly, let’s formulate equations for the rules for each number between 1 and 9 that occurs only once in each of the 9 columns.
Written in mathematical notation,
sum X for each j from 1 to 9 (for all I and k between 1 and 9) = 1
Written in detail for a few columns for each number between 1 and 9
column 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.
It must be filled in for all other numbers from 4 to 9.
column 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.
This must be completed for all other numbers from 4 to 9.
Let us now represent the small boxes (3 x 3) in total 9 squares in number.
So, in each 3 x 3 square, there should be only one 1 or 2 or 3 or 4 or 5 or 6 or 7 or 8 or 9, etc.,
The cells are between Columns (1 to 3) and Rows (1 to 3), Columns (4 to 6) and Rows (1 to 3) Columns (7 to 9) and Rows (1 to 3). Also for the same set of columns they occur in rows (4 to 6) and (6 to 9). So, let’s formulate the equations for a single small square located between the columns (1 to 3) and the rows (1 to 3). The corresponding decision variables for the digit “1” are (9 in total)
X111, X121, X131, X211, X221, X231, X311, X321, X331.
Let’s formulate the equation that this square (3 x3) has only one “1”.
then the equation is
X111 + X121+ X131 + X211 +X221+ X231+ X311 + X321 + X331 = 1.
The above equation would imply that only one of these 9 variables or only one of these nine cells can take the value 1.
Similarly, you have restrictions to formulate for the digit “2”, the digit “3”, and so on up to 9.
For integer programming problems, in addition to the equations that describe the constraints, you must also impose integer constraints on each and every variable so that eventually, when you solve the system of equations, you get a 0 or a 1 as a solution for the variable Xijk. .
The geometric equivalent of a linear programming problem with an objective function and some constraints is nothing more than a dimensional polyhedron where n represents the number of constraints in the problem. Usually the optimal solution will be found at the vertices of the polytope, also the rules of some methods like SIMPLEX will require that the polytope be convex so that one can traverse from vertex to vertex along the edges and find the optimal solution.
Further imposing integer constraints would mean that the optimal solution will not be at the vertices of the polytope since a solution found at the vertex may not be an integer. So, after taking into account that the optimal solution has to be either 0 or 1, it will mean that, geometrically, the solution will lie somewhere within the feasible region of the convex polytope and on one of the many straight lines originating from the polytope. hyperplane equivalent to Xi jk which has integer values.
Note that the solution above has used 729 decision variables and 81 row constraints. 81 column constraints and 729 small square constraints for a total of 901 constraints. There can be many objective functions, but an objective function can be formulated as finding the minimum of (sum of all 729 variables). You can reduce the number of constraints by finding some redundancy.
These above equations cannot be solved using programming languages such as Visual Basic, Pascal or C. Integer programming problems can be solved using optimization software such as CPLEX optimizer, Excel add-in for solving linear programming problems, Lingo, etc