A 9 X9 SUDOKU puzzle has the next guidelines. Each row and column ought to have the numbers between 1 and 9 and every of the internal bins ought to have the numbers between 1 and 9. Every quantity in each column and row and in each small field ought to happen solely as soon as.
Allow us to simply outline Xijk for all values of I, j and okay from 1 to 9 to be 1. If the cell (I,j) comprises the quantity okay the place I, j and okay all vary between 1 and 9. Right here I denotes the ith row and j denotes the jth column and okay denotes an integer between 1 and 9. When X134 = 1, it implies that the cell (1,3) comprises the quantity 4. This could additionally suggest that not one of the different components of the first row or the third column besides the cell (1,3) could be equal to 4.
With the intention to mannequin the SUDOKU we’ll use a complete of 729 variables.
Allow us to now algebraically formulate every of the three class of guidelines.
Each row ought to include a quantity between 1 and 9 precisely solely as soon as.
For the primary row, this rule would seem as ( termed as “Constraint” Within the language of Integer Programming).
for each I from 1 to 9 and for each okay from 1 to 9(I is a mathematical illustration of a counter variable)
sum (Xijk) for all j from 1 to 9 = 1;
Written in verbose kind for the first row for every quantity 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 comply with for variables beginning with X115 to X119.
Similary allow us to formulate equations for the foundations of every quantity between 1 and 9 occurring solely as soon as in every of the 9 columns.
Written in mathematical notation,
sum X for each j from 1 to 9 ( for all I and okay between 1 to 9 ) = 1
Written in verbose kind for just a few columns for every quantity 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 should be crammed up for all different 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 should be crammed up for all different numbers from 4 to 9.
Allow us to now signify the small bins ( 3 x 3 ) completely 9 squares in quantity.
So in every 3 x 3 sq., there should be just one 1 or 2 or 3 or 4 or 5 or 6 or 7 or 8 or 9 and many others.,
The cells happen between Columns ( 1 to three) and Rows ( 1 to three), Columns(4 to six) and Rows (1 to three) Columns (7 to 9) rows ( 1 to three). Additionally for a similar set of columns they happen in rows(4 to six) and (6 to 9). So allow us to formulate the equations for just one small sq. situated between columns(1 to three) and rows(1 to three). The corresponding choice variables for digit “1” are (9 in complete)
X111, X121, X131, X211,X221,X231,X311, X321,X331.
Allow us to formulate the equation that this (3 x3) sq. holds just one “1”.
So the equation is
X111 + X121+ X131 + X211 +X221+ X231+ X311 + X321 + X331 = 1.
The above equation would suggest that solely considered one of these 9 variables or solely considered one of these 9 cells can take the worth 1.
Equally constraints need to be formulated for the digit “2”, digit “3” so on till 9.
For integer programming issues along with equations describing the constraints, there must also be integer constraints imposed on every variable in order that finally when the system of equations are solved, one will get both a 0 or a 1 as the answer to the variable Xijk.
The geometric equal of a linear programming drawback with an goal operate and a few constraints is nothing however a n dimensional polyhedron the place n represents the variety of constraints in the issue. Normally the optimum answer shall be discovered on the vertexes of the polytope, additionally the foundations of some methodology resembling SIMPLEX would require that the polytope is convex in order that one can traverse from vertex to vertex alongside the perimeters and discover out the optimum answer.
Imposing integer constraints as well as would imply that the optimum answer is not going to be on the vertices of the polytope as an answer discovered on the vertex might not be an integer. So after taking into consideration that the optimum answer must be 0 or 1 will imply that geometrically the answer shall be someplace contained in the possible area of the convex polytope and on one of many many straight traces originating from the hyperplane equal to Xi j okay having integer values.
A word that the answer above has used 729 choice variables and 81 row constraints. 81 column constraints and 729 small sq. constraints totalling 901 constraints. There could be many goal capabilities, however one can formulate an goal operate as discovering the min of ( sum of all of the 729 variables). One can cut back the variety of constraints by discovering some redundancy.
These equations above can’t be solved utilizing programming languages resembling Visible Fundamental, Pascal or C. Integer programming issues could be solved utilizing optimization software program resembling CPLEX optimizer, Excel addin for fixing Linear Programming issues, Lingo and many others.
