Solve Sudoku using integer programming

A 9 X9 Sudoku puzzle has the following rules. Each row and column must have numbers between 1 and 9, and each of the inner squares must have numbers between 1 and 9. Each number in each column, every row, and every small square must occur only once.

Let's just set Xijk for all values ​​of I, j, and k from 1 to 9 to be 1. If cell (I, j) contains the number k where all I, j and k are between 1 and 9. I refer to row ith and j To column jth and k denotes an integer between 1 and 9. When X134 = 1, this means that cell (1,3) contains the number 4. This also means that neither one can equal the elements of the first row or the third column except Cell (1,3) 4.

For SUDOKU modeling, we'll use a total of 729 variables.

Let us now perform algebraic formatting for each of the three rules.

Each row must contain a number between 1 and 9 only once.

For the first row, this rule will appear as (known as a "constraint" in the correct programming language).

For every I from 1 to 9 and for every k from 1 to 9 (I is a mathematical representation of the counter variable)

sum (Xijk) for all j from 1 to 9 = 1;

Written in length for the first 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 variables from X115 to X119.

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

Written in mathematical notation,

Sum of X per j from 1 to 9 (per I and k between 1 to 9) = 1

Written in length for a few columns per 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 number must be filled in 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 number must be filled in for all other numbers 4 to 9.

Now let's represent the small boxes (3 x 3) 9 squares in number.

So in every 3 x 3 square meters there should be one, 2, 3, 4, 5, 6, 7, 8, 9, etc.

Cells occur between columns (1 to 3) and rows (1 to 3), columns (4 to 6) and rows (1 to 3) from columns (7 to 9) from rows (1 to 3). Also the same set of columns occurs in rows (4 to 6) and (6 to 9). So let's just formulate equations for just one small square that falls between columns (1 to 3) and rows (1 to 3). Resolution variables corresponding to the number "1" are (9 in total)

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

Let's just formulate the equation in this square (3 x 3) with just one "1".

So the equation is

X111 + X121 + X131 + X211 + X221 + X231 + X311 + X321 + X331 = 1.

The above equation indicates that only one of these 9 variables or only one of these nine cells can take the value 1.

Likewise, restrictions should be made for the number "2", the number "3", and so on until 9.

In terms of correct programming problems as well as equations describing constraints, integer constraints must also be imposed on each variable so that equations are ultimately solved when the system of equations gets 0 or 1 as a solution to the Xijk variable.

The geometric equivalent of a linear programming problem with an objective function and some constraints is only a multidimensional anthropomorphic where n represents the number of constraints in the problem. The optimal solution is usually found on the tops of the polytope, and the rules of some methods such as SIMPLEX require that the polytope be convex so that one can move from the vertex to the vertex on the edges and know the optimal solution.

In addition, imposing integer constraints means that the optimal solution will not be on the polytope heads since the solution on the head may not be an integer. So, after considering that the optimal solution should be 0 or 1 would mean that the solution would be geometrical somewhere within the possible region of the convex polytope and on one of many straight lines generated by the equivalent Hybridplane of Xi jk with integer values.

Note that the above solution may use 729 decision variables and 81 row limitations. 81 column restrictions and 729 small square restrictions, total 901 restrictions. There can be many objective functions, but one can formulate an objective function like finding min (sum of all variables 729). One can reduce a number of limitations by finding some repetition.

These above equations cannot be solved using programming languages ​​like Visual Basic, Pascal or C. Integer programming problems can be solved by using optimization software like CPLEX optimizer and addin Excel to solve linear programming problems, Lingo etc.

&

    Leave Your Comment

    Your email address will not be published.*