【转载】SUDOKU 游戏的GAMS 版本

huashi3483

随便发一个sudoku的gams代码。最主要的是请大家理解set 里面mapping 的写法。
Sets  r  rows    / r1*r9 /
      c  columns / c1*c9 /
      b  blocks  / b1*b9 /
5 e" `1 Z1 L' J: w' z  G0 [      v  values  / v1*v9 /
      br(b,r)    /  b1*b3    .r1*r3,  b4*b6    .r4*r6,  b7*b9    .r7*r9 /
      bc(b,c)    / (b1,b4,b7).c1*c3, (b2,b5,b8).c4*c6, (b3,b6,b9).c7*c9 /
  A3 P) o1 k# I$ D6 w9 @/ s2 P5 p      brc(b,r,c) block definitions ;

  D0 y8 t: v& F8 S% E8 Lbrc(b,r,c) = br(b,r)*bc(b,c);

) s2 \- j- b# h/ D" xTable problem(r,c) Hard problem with non-unique solution
$ b$ W3 a' W7 ~) x% T    c1   c2   c3   c4   c5   c6   c7   c8   c9
  Y* X3 B; P/ i, c: Lr1   2              6    7
4 s" D" ?0 o# ?0 Lr2            6                    2
r3   4                             8         1
r4   5                        9    3
. D3 M/ f  C5 H& `7 w' c! Br5        3                             5
9 t+ _, c7 }' f) h+ Y+ h! I& {r6             2    8                        7
r7             1
1 j8 j/ a/ y" C1 [r8   7         8                   6
r9                       5    3              8 ;
& O/ H9 z+ s+ g. k: x
; C( H: ^6 f1 o: f4 B
1 z5 \/ f* w8 \" t4 ]# }  {Binary Variable X(r,c,v) assign value to cell (defined by row and column);
Variable        W        objectiv value - anything;

equations eq1(r,c) exactly one value for each cell
* G7 ?4 P; a5 J% A( S4 N          eq2(c,v) column entries have to be unique
          eq3(r,v) row entries have to be unique
          eq4(b,v) block entries have to be unique
          nobj     definition of objective - anything;

X.fx(r,c,v)$(problem(r,c)=ord(v)) = 1;
% _) A8 X4 ~  h3 b( U6 f  o
4 c2 q; d9 t$ {, j$ a6 q% V( heq1(r,c).. sum(v, X(r,c,v))          =E= 1;
eq2(c,v).. sum(r, X(r,c,v))          =E= 1;
: r: I( H% z" geq3(r,v).. sum(c, X(r,c,v))          =E= 1;
eq4(b,v).. sum(brc(b,r,c), X(r,c,v)) =E= 1;
nobj..     W =E= sum((r,c,v), X(r,c,v));

model sudoku / all /;
1 V5 \0 ~$ {: |3 M/ x) E/ d
% C& X5 m" ^0 d& `/ dsolve sudoku minimizing w using mip;
最后说一句，其实这个模型不用求什么最大还是最小值，只要得到一个满足所有constraints的feasible solution 就可以了，所以nobj的注释写的"anything"。