Solving the Sudoku Using Integer Programming

[ad_1]

A 9 X9 SUDOKU puzzle has the following rules. Every row and column should have the numbers between 1 and 9 and each of the inner boxes should have the numbers between 1 and 9. Each number in every column and row and in every small box should occur only once.

Let us just define Xijk for all values of I, j and k from 1 to 9 to be 1. If the cell (I,j) contains the number k where I, j and k all range between 1 and 9. Here I denotes the ith row and j denotes the jth column and k denotes an integer between 1 and 9. When X134 = 1, it means that the cell (1,3) contains the number 4. This would also imply that none of the other elements of the 1st row or the 3rd column except the cell (1,3) can be equal to 4.

In order to model the SUDOKU we will use a total of 729 variables.

Let us now algebraically formulate each of the three class of rules.

Every row should contain a number between 1 and 9 exactly only once.

For the first row, this rule would appear as ( termed as “Constraint” In the language of Integer Programming).

for every I from 1 to 9 and for every 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 1st row for 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 starting with X115 to X119.

Similary let us formulate equations for the rules of each number between 1 and 9 occurring only once in each of the 9 columns.

Written in mathematical notation,

sum X for every j from 1 to 9 ( for all I and k between 1 to 9 ) = 1

Written in verbose form 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.

This must be filled up for all other numbers 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 filled up for all other numbers from 4 to 9.

Let us now represent the small boxes ( 3 x 3 ) totally 9 squares in number.

So in each 3 x 3 square, there must be only one 1 or 2 or 3 or 4 or 5 or 6 or 7 or 8 or 9 etc.,

The cells occur between Columns ( 1 to 3) and Rows ( 1 to 3), Columns(4 to 6) and Rows (1 to 3) Columns (7 to 9) rows ( 1 to 3). Also for the same set of columns they occur in rows(4 to 6) and (6 to 9). So let us formulate the equations for only one small square located between columns(1 to 3) and rows(1 to 3). The corresponding decision variables for digit “1” are (9 in total)

X111, X121, X131, X211,X221,X231,X311, X321,X331.

Let us formulate the equation that this (3 x3) square holds only one “1”.

So 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 constraints have to be formulated for the digit “2”, digit “3” so on until 9.

For integer programming problems in addition to equations describing the constraints, there should also be integer constraints imposed on each and every variable so that eventually when the system of equations are solved, one gets either a 0 or a 1 as the solution to the variable Xijk.

The geometric equivalent of a linear programming problem with an objective function and some constraints is nothing but a n dimensional polyhedron where n represents the number of constraints in the problem. Usually the optimum solution will be found on the vertexes of the polytope, also the rules of some method such as SIMPLEX will require that the polytope is convex so that one can traverse from vertex to vertex along the edges and find out the optimum solution.

Imposing integer constraints in addition would mean that the optimal solution will not be on the vertices of the polytope as a solution found on the vertex may not be an integer. So after taking into account that the optimum solution has to be 0 or 1 will mean that geometrically the solution will be somewhere inside the feasible region of the convex polytope and on one of the many straight lines originating from the hyperplane equivalent to Xi j k having integer values.

A note that the solution above has used 729 decision variables and 81 row constraints. 81 column constraints and 729 small square constraints totalling 901 constraints. There can be many objective functions, but one can formulate an objective function as finding the min of ( sum of all the 729 variables). One can reduce the number of constraints by finding some redundancy.

These equations above 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 addin for solving Linear Programming problems, Lingo etc.

[ad_2]

Source by Srinivasa Gopal