【转载】SUDOKU 游戏的GAMS 版本

huashi3483

随便发一个sudoku的gams代码。最主要的是请大家理解set 里面mapping 的写法。
Sets  r  rows    / r1*r9 /
" D- {" E% I* q# I      c  columns / c1*c9 /
3 a" J/ T) o% W* b! n      b  blocks  / b1*b9 /
  _5 z# d. u! \6 a; E      v  values  / v1*v9 /
1 b7 Z% R8 g5 f; e. L3 v      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 /
      brc(b,r,c) block definitions ;

+ m3 C) \; @) N& ?) `$ w6 `brc(b,r,c) = br(b,r)*bc(b,c);

6 A; }0 u- h3 N$ j6 V7 ITable problem(r,c) Hard problem with non-unique solution
; J( F& U6 o# Y2 X2 ^; S: a    c1   c2   c3   c4   c5   c6   c7   c8   c9
+ _# |  P# I8 y5 c; Hr1   2              6    7
+ ~' x6 u3 h2 i& K6 Wr2            6                    2
4 i$ {0 y! j* Z; z! G% T' I5 Rr3   4                             8         1
r4   5                        9    3
r5        3                             5
0 D3 }  ?- s- G6 T  N) O4 }r6             2    8                        7
& i3 `: [# a6 z8 Q5 ur7             1
* T- d) ?$ P, Tr8   7         8                   6
r9                       5    3              8 ;


, W- l9 i0 s3 E: `# OBinary Variable X(r,c,v) assign value to cell (defined by row and column);
Variable        W        objectiv value - anything;

' Z1 `7 h/ g! a' G* k) e& L0 qequations eq1(r,c) exactly one value for each cell
6 g0 g8 Y- C, l* k- K          eq2(c,v) column entries have to be unique
( ^% ]6 X8 t8 j          eq3(r,v) row entries have to be unique
          eq4(b,v) block entries have to be unique
( k  u3 _: _3 a# Z2 K& b/ e          nobj     definition of objective - anything;

& @' @. s7 h' \, ]% S7 o5 t5 f' q& rX.fx(r,c,v)$(problem(r,c)=ord(v)) = 1;

eq1(r,c).. sum(v, X(r,c,v))          =E= 1;
; ]2 v6 u) o/ z7 d: Q9 V2 o) d. `eq2(c,v).. sum(r, X(r,c,v))          =E= 1;
eq3(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));
$ d3 r! i5 R) G
  W, x3 s. X/ R# Nmodel sudoku / all /;
: I* s# X1 x+ [. X: |3 v, c
solve sudoku minimizing w using mip;
( N# N8 A5 f( N最后说一句，其实这个模型不用求什么最大还是最小值，只要得到一个满足所有constraints的feasible solution 就可以了，所以nobj的注释写的"anything"。