Home Hacker News Solving Sudoku as an integer programming problem
Solving Sudoku as an integer programming problem

Solving Sudoku as an integer programming problem

0
0


It is fairly straight forward to solve a Sudoku as an integer programming problem, by creating 9 binary variables for each cell, only one of which is one in the solution. The walk-through below and attached notebook illustrates this for the problem shown.

Given values, as {row, column, value}

input = {
{1,4,4},{1,5,9},{1,8,5},{2,1,6},{2,5,3},{3,1,4},
{3,2,5},{3,4,6},{3,5,2},{3,7,3},{3,9,7},{4,1,5},
{4,3,2},{4,4,7},{4,7,9},{4,8,8},{5,1,3},{5,3,6},
{5,7,2},{5,9,1},{6,2,9},{6,3,1},{6,6,2},{6,7,6},
{6,9,5},{7,1,2},{7,3,5},{7,5,1},{7,6,4},{7,8,3},
{7,9,8},{8,5,8},{8,9,9},{9,2,1},{9,5,7},{9,6,3}};

Display given values

viewmat = Table["", {9}, {9}];    
Do[viewmat[[input[[i, 1]], input[[i, 2]]]] = ToString[input[[i, 3]]], {i, Length[input]}]
Grid[viewmat, Frame -> All]

enter image description here

Variables, as 9 x 9 x 9 matrix

varmat = Table[m[i, j, k], {i, 9}, {j, 9}, {k, 9}];

Variables as a list

vars = Flatten[varmat];

Constrain the input cells to their value

cons1 = (varmat[[Sequence @@ #]] == 1 &) /@ input

enter image description here

The sum of the binary variables for each cell is 1

cons2 = Flatten @ Table[ (Sum[varmat[[i, j, k]], {k, 9}] == 1), {i, 9}, {j, 9}];

All different constraint for the rows

cons3 = Flatten @ Table[ (Sum[varmat[[i, j, k]], {i, 9}] == 1), {j, 9}, {k, 9}];

All different constraint for the columns

cons4 = Flatten @ Table[ (Sum[varmat[[i, j, k]], {j, 9}] == 1), {i, 9}, {k, 9}];

All different constraint for the submatrices

sm[di_, dj_] := Flatten [Table[{i, j}, {i, 1 + 3*(di - 1), 3*di}, {j, 1 + 3*(dj - 1), 3*dj}],1]
cons5 = Flatten @ Table[(Total[m[Sequence @@ #, k] & /@ sm[i, j]] == 1), {i, 3}, {j, 3}, {k, 9}];

Confine the variables to the range 0 to 1

cons6 = Thread[0 <= vars <= 1];

Combine the constraints

Length[allcons = Join[cons1, cons2, cons3, cons4, cons5, cons6]]

1089

Solve the problem, specifying that the variables are integers.

AbsoluteTiming[sol = FindMinimum[{0, allcons, Element[vars, Integers]}, vars];]

{0.0946335, Null}

Find the values for each cell

resmat = Table[Sum[k*m[i, j, k], {k, 9}], {i, 9}, {j, 9}] /. sol[[2]]

enter image description here

Display the input and result

{Grid[viewmat, Frame -> All], Grid[resmat, Frame -> All]}

enter image description here

Check the result

And @@ Table[Unequal[Sequence @@ resmat[[i]]], {i, 9}]

True

And @@ Table[Unequal[Sequence @@ Transpose[resmat][[i]]], {i, 9}]

True

And @@ Flatten @ Table[Unequal[resmat[[Sequence @@ #]] & /@ sm[i, j]], {i, 3}, {j, 3}]

True

Attachments:



Source link

LEAVE YOUR COMMENT

Your email address will not be published. Required fields are marked *

WordPress Anti Spam by WP-SpamShield

Close

Powered by moviekillers.com