【转载】SUDOKU 游戏的GAMS 版本

huashi3483

随便发一个sudoku的gams代码。最主要的是请大家理解set 里面mapping 的写法。
& m& N, a* A) y$ G9 U- `6 D& aSets  r  rows    / r1*r9 /
      c  columns / c1*c9 /
! R, n  S( D0 \. y1 l      b  blocks  / b1*b9 /
8 z) O/ z7 `3 d6 f      v  values  / v1*v9 /
      br(b,r)    /  b1*b3    .r1*r3,  b4*b6    .r4*r6,  b7*b9    .r7*r9 /
* Z& M# \# }) W. u) R* @" |9 g: v      bc(b,c)    / (b1,b4,b7).c1*c3, (b2,b5,b8).c4*c6, (b3,b6,b9).c7*c9 /
# O2 s2 y. w  I7 {' J      brc(b,r,c) block definitions ;
9 M. g  Q7 e3 _" x
brc(b,r,c) = br(b,r)*bc(b,c);
8 d; U, m% H! E" ?; U
( K  }- I+ N$ X* V! e# VTable problem(r,c) Hard problem with non-unique solution
    c1   c2   c3   c4   c5   c6   c7   c8   c9
r1   2              6    7
0 @) M% Z% l* L1 P' Z0 H" ir2            6                    2
6 X# {3 w, M3 c0 m9 U( br3   4                             8         1
r4   5                        9    3
r5        3                             5
, m/ @3 O  L' E  t, M% u( Vr6             2    8                        7
r7             1
r8   7         8                   6
r9                       5    3              8 ;
: W* R/ W, ^+ L7 c

% |  X: p7 P# n+ d0 l7 e2 ZBinary Variable X(r,c,v) assign value to cell (defined by row and column);
Variable        W        objectiv value - anything;

9 ^" j, f" t1 j! M8 ^0 n+ _equations eq1(r,c) exactly one value for each cell
          eq2(c,v) column entries have to be unique
8 @" k* B+ ]9 v% r# \  P          eq3(r,v) row entries have to be unique
' L; q6 M. O3 W& J5 {! q' l          eq4(b,v) block entries have to be unique
' y' \% w' Q0 Y( ?- d5 f& D          nobj     definition of objective - anything;

7 o3 z. f8 m2 eX.fx(r,c,v)$(problem(r,c)=ord(v)) = 1;
0 l; E. C  }2 b1 d# f. D
eq1(r,c).. sum(v, X(r,c,v))          =E= 1;
9 w% l( y$ T$ W2 Weq2(c,v).. sum(r, X(r,c,v))          =E= 1;
' y5 s% ~7 r2 S' H2 R: X5 S1 Z" u4 aeq3(r,v).. sum(c, X(r,c,v))          =E= 1;
eq4(b,v).. sum(brc(b,r,c), X(r,c,v)) =E= 1;
" `) Y4 A/ L, Y' x7 x( c% Q1 Pnobj..     W =E= sum((r,c,v), X(r,c,v));
9 K3 @) b, e1 h8 o4 t5 S" [/ B
model sudoku / all /;

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