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.