## Monday, November 10, 2008

### Sudoku: Constraint Programming vs MIP

The Sudoku puzzle can be coded easily using constraint programming thanks to built-in constructs that handle the all-different constraint. Here is an example using the Microsoft Solver Foundation CSP solver:

The only difficulty was to model: for all i,j such that d[i,j]>0 require that x[i,j]=d[i,j]. I used the following formulation: Foreach[{i,I},{j,J},x[i,j]==d[i,j] | d[i,j]==0] where | is an "or" operator.

The complete model looks like:
``Model[   Parameters[Sets,I,J],  Parameters[Integers,d[I,J]],   Decisions[Integers[1,9],x[I,J]],   Constraints[     // Alternative 1: (does not work in the beta)    //FilteredForeach[{i,I},{j,J},d[i,j]>0,x[i,j]==d[i,j]],    // Alternative 2:     Foreach[{i,I},{j,J},x[i,j]==d[i,j] | d[i,j]==0],     Foreach[{i,I},Unequal[Foreach[{j,J},x[i,j]]]],    Foreach[{j,J},Unequal[Foreach[{i,I},x[i,j]]]],      Foreach[{ib,3},        Foreach[{jb,3},            Unequal[Foreach[{i,ib*3,ib*3+3},{j,jb*3,jb*3+3},x[i,j]]]         ]    ]  ] ]``

The above sudoku can also be coded in GAMS:

``\$ontext  Sudoku solver  September 2005   Code written by:     Paul van der Eijk     GAMS Development Corporation     1217 Potomac Street NW     Washington DC, 20007     Tel: (202) 342-0180 Fax: (202) 342-0181     Email: paul@gams.com     WWW: http://www.gams.com   Based on Latin Square example in GAMS model library.   Adapted to solve a Sudoku problem by:     Sherman Robinson     Economics Department     University of Sussex     Brighton BN1 9SN     UK     email: sherman.robinson@sussex.ac.uk  \$offtext sets r  rows    / r1 * r9/ c  columns / c1 * c9/ v  values  / v1 * v9/ sc sub-col /sc1 * sc3/ sr sub-row /sr1 * sr3/ scs(sc, c) /sc1.(c1*c3), sc2.(c4*c6), sc3.(c7*c9)/ srs(sr, r) /sr1.(r1*r3), sr2.(r4*r6), sr3.(r7*r9)/; table problem(r,c)      c1  c2  c3  c4  c5  c6  c7  c8  c9r1     5   3           7r2     6           1   9   5r3         9   8                   6r4     8               6               3r5     4           8       3           1r6     7               2               6r7         6                   2   8r8                 4   1   9           5r9                     8           7   9;display problem; Parameter  value(v) "Values";value(v) = ord(v) ; binary variable x(r,c,v);variable w;equations  eq1(r,c)        "exactly one value for each cell"  eq2(c, v)       "columns entries have to be unique"  eq3(r, v)       "row entries have to be unique"  eq4(sr, sc, v)  "sub-squares have to be unique"  nobj            "definition of objective - anything"; eq1(r, c)..   sum(v, x(r, c, v)) =E= 1;eq2(c, v)..   sum(r, x(r, c, v)) =E= 1;eq3(r, v)..   sum(c, x(r, c, v)) =E= 1;eq4(sr, sc, v).. sum((c,r)\$(scs(sc, c) and srs(sr, r)), x(r, c, v)) =E= 1; nobj..      w =E= sum((r, c, v), x(r, c, v)); *SR Fix values in the problemx.l(r,c,v)\$(problem(r,c) = value(v)) = 1 ;x.fx(r,c,v)\$(x.l(r,c,v) = 1)         = 1 ; option limrow=1000, limcol=0;option mip=cplex;model sudoku /eq1, eq2, eq3, eq4, nobj/;solve sudoku minimizing w using mip; parameter  solution(r,c)   "Display of results";loop(v,  solution(r, c)\$(x.l(r, c, v)) = Ord(v););option solution:0:1:1;display solution;``

I wrote an Excel based GUI for this model as an example, see http://www.amsterdamoptimization.com/packaging.html.