【转载】SUDOKU 游戏的GAMS 版本

huashi3483

随便发一个sudoku的gams代码。最主要的是请大家理解set 里面mapping 的写法。
Sets  r  rows    / r1*r9 /
      c  columns / c1*c9 /
      b  blocks  / b1*b9 /
( [  ]: L+ n! c5 s( z5 d      v  values  / v1*v9 /
& w. d% Q+ o3 z) Z% d- k1 m      br(b,r)    /  b1*b3    .r1*r3,  b4*b6    .r4*r6,  b7*b9    .r7*r9 /
6 m' o6 Q2 L9 I4 Y# \1 B; f# L- Y- _' G      bc(b,c)    / (b1,b4,b7).c1*c3, (b2,b5,b8).c4*c6, (b3,b6,b9).c7*c9 /
% h1 G4 k' m, q/ h. D8 D" ]) g6 G      brc(b,r,c) block definitions ;
) k0 Y* x) t7 C' m
+ B& M8 j- l1 J  {1 k: }2 T5 Cbrc(b,r,c) = br(b,r)*bc(b,c);
1 Q# g5 o4 n7 u" H/ J$ _. T
' A% F" [0 Q- G8 E/ ~Table problem(r,c) Hard problem with non-unique solution
# e5 A" e; c/ t0 F: f- c6 [    c1   c2   c3   c4   c5   c6   c7   c8   c9
r1   2              6    7
r2            6                    2
r3   4                             8         1
r4   5                        9    3
# o$ |& G, h' k8 Y& f2 ]* ir5        3                             5
r6             2    8                        7
' z& Y1 a9 C/ ^3 F9 hr7             1
$ Q# t: O. M' N% D+ rr8   7         8                   6
* X+ l- B; _( Z& A# w. m0 ^r9                       5    3              8 ;

  @) v) i- L  {! y0 X
: _; l" j$ U8 R2 E: \Binary Variable X(r,c,v) assign value to cell (defined by row and column);
8 K9 G7 F' B  p' @* bVariable        W        objectiv value - anything;
8 L; x- N  P; w. D
equations eq1(r,c) exactly one value for each cell
          eq2(c,v) column entries have to be unique
          eq3(r,v) row entries have to be unique
) b, c* e' A; ]. J& x          eq4(b,v) block entries have to be unique
3 d2 K; ], U+ P. Y          nobj     definition of objective - anything;

, L2 ~1 x2 n; q2 `. t  X4 bX.fx(r,c,v)$(problem(r,c)=ord(v)) = 1;

6 p( P  n' L' ~8 l5 c. Peq1(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;
, W3 c  D% j4 Zeq4(b,v).. sum(brc(b,r,c), X(r,c,v)) =E= 1;
nobj..     W =E= sum((r,c,v), X(r,c,v));

: j4 j: v- G4 X: k! _model sudoku / all /;

solve sudoku minimizing w using mip;
7 `7 Z8 Y5 g% h' k最后说一句，其实这个模型不用求什么最大还是最小值，只要得到一个满足所有constraints的feasible solution 就可以了，所以nobj的注释写的"anything"。