Re: FindInstance for sudoku

*To*: mathgroup at smc.vnet.net*Subject*: [mg64847] Re: [mg64808] FindInstance for sudoku*From*: Daniel Lichtblau <danl at wolfram.com>*Date*: Sun, 5 Mar 2006 03:19:16 -0500 (EST)*References*: <200603040735.CAA15772@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

Arturas Acus wrote: > Dear group, > > Despite there was a number of solutions of sudoku puzzle presented on > the list half a year ago, I decided to check if it can be handled in a > pure algebraic way with current Mathematica solvers. (As far as I remember, all > previously mentioned solutions was of different kind). > > Unfortunatelly after playing a bit I was unable to find a satisfactory > approach. I am still interesting weather combination of obvious > algebraic conditions can yield any solution using current Mathematica solvers. > > Below is some of my attempts: > > > (* general definitions *) > > sudokuForm[mat_]:= > DisplayForm[ > GridBox[Map[GridBox,mat,{2}],GridFrame->True,RowLines->True, > ColumnLines->True]] > sudokuQ[mat_]:=Dimensions[mat]==={3,3,3,3} > > sudokuGeneral=Table[Table[elem[i,j][m,n],{m,3},{n,3}],{i,3},{j,3}] > > sudokuForm[sudokuGeneral] > > > (* obviuos conditions we can formulate sudoku puzzle in algebraic way *) > (* first two indices (i-raw,j-column) enumerates big boxes; other (m,n) > enumerates elements inside (i,j) box*) > > plusBoxesConditions= > Thread[Equal[Flatten[Table[Sum[elem[i,j][m,n],{n,3},{m,3}],{i,3},{j,3}]], > 45]]; > > plusRawsConditions= > Thread[Equal[Flatten[Table[Sum[elem[i,j][m,n],{j,3},{n,3}],{i,3},{m,3}]], > 45]]; > > plusColumnsConditions= > Thread[Equal[Flatten[Table[Sum[elem[i,j][m,n],{i,3},{m,3}],{j,3},{n,3}]], > 45]]; > > timesRawsConditions= > Thread[Equal[ > Flatten[Table[Product[elem[i,j][m,n],{j,3},{n,3}],{i,3},{m,3}]],9!]]; > > timesColumnsConditions= > Thread[Equal[ > Flatten[Table[Product[elem[i,j][m,n],{i,3},{m,3}],{j,3},{n,3}]],9!]]; > > > integerConditions= > Thread[Equal[Apply[Times,Map[(#-Range[9])&,Flatten[sudokuGeneral]],{1}], > 0]]; > > noZerosCondition=(Times@@Flatten[sudokuGeneral]==Factorial[9]^9); > > allSudokuConditions= > Flatten[{plusRawsConditions,plusColumnsConditions,plusBoxesConditions,noZerosCondition}]; > > > (* sudoku sample: zeros are empty boxes *) > > sudokuSample = > {{{{0, 0, 1}, {0, 7, 0}, {3, 0, 0}}, {{0, 0, 0}, {3, 1, 0}, {0,4, 5}}, > {{8, 0, 0}, {0, 9, 0}, {0, 0, 7}}}, > {{{0, 9, 0}, {0, 4, 2}, {0, 0, 3}}, {{7, 0, 0}, {0, 5, 0}, {0, 0, 9}}, > {{5, 0, 0}, {1, 3, 0}, {0, 4, 0}}}, > {{{2, 0, 0}, {0, 3, 0}, {0, 0, 4}}, {{5, 7, 0}, {0, 9, 1}, {0, 0, 0}}, > {{0, 0, 4}, {0, 6, 0}, {3, 0, 0}}}}; > > sudokuForm[sudokuSample] > > (* try to form simplest equation set: depends of what conditions to > include*) > > allEq = DeleteCases[ > allSudokuConditions /. > Evaluate[DeleteCases[ > Flatten[MapThread[Rule, {sudokuGeneral, sudokuSample}, 4]], > Rule[_, 0]]], True] > > vars = DeleteCases[ > Flatten[sudokuGeneral] /. > Evaluate[DeleteCases[ > Flatten[MapThread[Rule, {sudokuGeneral, sudokuSample}, 4]], > Rule[_, 0]]], _Integer] > > > Length/@{allEq,vars} > Out[46]= > {28,50} > > > sol = FindInstance[allEq, vars, Integers] > > ?Modulus->10? > (* FindInstance seems to be most promising. Rezult: exit after all 256 > Mb memory being exhausted*) Certainly sudoku can be cast as a FindInstance problem. That said, I cannot imagine it actually giving a result when the equations are by and large nonlinear or are heavily underdetetmined. A good way to use FindInstance for sudoku is by formulating as a knapsack integer programming problem with variables taking on 0-1 values. When I tried this with FindInstance last May some problems arose in that the underlying relaxed LP solver was too slow. The issue, roughly and as best I understand, is that we are using an exact simplex method that is not taking advantage of potential use of finite precision in intermediate steps. One can instead code a branch-and-bound and/or cutting plane approach to the knapsack solver, using explicit finite precision LP solver beneath the surface (and taking responsibility for precision issues). If done with some reasonable preprocessing heuristics, 9x9 examples are solved quite fast, and in many cases (yours is one such) will not even reach the branch-and-bound or cutting plane loop. I recoded your input to be in row form as that seems to be vastly more common, not to mention unambiguous in terms of being independent of how you order the blocks. I use "sparseArray" as a dummy head that looks like SparseArray, and has a vaguely similar meaning, but is not in fact a Mathematica SparseArray data object. sudokuSample = sparseArray[{ {1,3}->1, {1,7}->8, {2,2}->7, {2,4}->3, {2,5}->1, {3,1}->3, {3,5}->4, {3,6}->5, {3,9}->7, {4,2}->9, {4,4}->7, {4,7}->5, {5,2}->4, {5,3}->2, {5,5}->5, {5,7}->1, {5,8}->3, {6,3}->3, {6,6}->9, {6,8}->4, {7,1}->2, {7,4}->5, {7,5}->7, {7,9}->4, {8,2}->3, {8,5}->9, {8,6}->1, {8,8}->6, {9,3}->4, {9,7}->3 }] Timing[res = sudoku[sudokuSample]] Out[5]= {0.076004 Second, {0, {{4, 2, 1, 9, 6, 7, 8, 5, 3}, {6, 7, 5, 3, 1, 8, 4, 9, 2}, {3, 8, 9, 2, 4, 5, 6, 1, 7}, {1, 9, 8, 7, 3, 4, 5, 2, 6}, {7, 4, 2, 8, 5, 6, 1, 3, 9}, {5, 6, 3, 1, 2, 9, 7, 4, 8}, {2, 1, 6, 5, 7, 3, 9, 8, 4}, {8, 3, 7, 4, 9, 1, 2, 6, 5}, {9, 5, 4, 6, 8, 2, 3, 7, 1}}}} At some point a couple of us are thinking we might write up the details, code and some related work for an article for The Mathematica Journal. I will say here that for larger examples it might not compete very well with the sudoku solver recently presented by Fred Simons in Mathematica in Education and Research. His was based on an explicit backtrack mechanism as opposed to equation solving. The 16x16 example he presented was managed in a few seconds. That can also be achieved with integer linear programming methods but they appear to require more sophistication (with cutting planes, I think) than I have at hand. The best I could do on the same example, without recourse to voodoo, was around a minute. (Linking to a dedicated ILP solver in the COIN-OR library brought this to a few seconds, which is how I know "good" ILP can do better than I can.) Daniel Lichtblau Wolfram Research

**References**:**FindInstance for sudoku***From:*Arturas Acus <acus@itpa.lt>