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:

 

(click to enlarge)

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  c9
r1     5   3           7
r2     6           1   9   5
r3         9   8                   6
r4     8               6               3
r5     4           8       3           1
r6     7               2               6
r7         6                   2   8
r8                 4   1   9           5
r9                     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 problem
x.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.