【转载】SUDOKU 游戏的GAMS 版本

huashi3483

随便发一个sudoku的gams代码。最主要的是请大家理解set 里面mapping 的写法。
Sets  r  rows    / r1*r9 /
* \# [4 k4 O/ v+ W      c  columns / c1*c9 /
      b  blocks  / b1*b9 /
      v  values  / v1*v9 /
      br(b,r)    /  b1*b3    .r1*r3,  b4*b6    .r4*r6,  b7*b9    .r7*r9 /
4 n% d& ~& }, m% H2 m* K& H" m3 x( I# t      bc(b,c)    / (b1,b4,b7).c1*c3, (b2,b5,b8).c4*c6, (b3,b6,b9).c7*c9 /
      brc(b,r,c) block definitions ;
" y, M2 n6 h7 s  t" y8 b+ ]
* }7 R( z( a3 k2 Jbrc(b,r,c) = br(b,r)*bc(b,c);
0 l2 c+ @" l# M- v) @5 Z; K
  a9 y0 q+ d, ^1 F" ZTable problem(r,c) Hard problem with non-unique solution
& [) H& L. Z# p4 d    c1   c2   c3   c4   c5   c6   c7   c8   c9
r1   2              6    7
r2            6                    2
, M% M4 n/ \& R0 y# ]5 O/ Nr3   4                             8         1
$ |3 e3 H3 R( X$ qr4   5                        9    3
( i, M1 h) l7 Y  c4 nr5        3                             5
r6             2    8                        7
r7             1
2 w2 K3 [. ?1 ^( p4 t' er8   7         8                   6
- V# }6 T" j% a9 z- Or9                       5    3              8 ;
- Z& o1 n: w5 U' q7 h! G% D+ X% H

Binary Variable X(r,c,v) assign value to cell (defined by row and column);
5 l& Y; d2 f. hVariable        W        objectiv value - anything;
$ z: U7 `# {' r+ p, e
2 J- ^5 m& C* }! z8 b0 Yequations eq1(r,c) exactly one value for each cell
          eq2(c,v) column entries have to be unique
9 Y7 k1 m$ X+ y9 `; r          eq3(r,v) row entries have to be unique
/ Y% _. F/ @& P1 f9 I) E3 K( X3 u  t          eq4(b,v) block entries have to be unique
" N; y! [- a; T; M5 {; l          nobj     definition of objective - anything;

6 a! a2 r( ~- y) }X.fx(r,c,v)$(problem(r,c)=ord(v)) = 1;
- y! N2 l( J7 f  \( b8 i2 Q6 p* [
2 i) Q, [. {! b* Veq1(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(b,v).. sum(brc(b,r,c), X(r,c,v)) =E= 1;
8 K% T$ Y! N/ P& |4 i& V; unobj..     W =E= sum((r,c,v), X(r,c,v));
1 G' X! s2 I  Z6 g  k/ n+ `
model sudoku / all /;
3 ~2 A$ `2 ~- L/ S$ `2 O  I2 W. \
: k1 ]1 L* W- m8 bsolve sudoku minimizing w using mip;
' ~9 C! z0 _# L1 L' \3 A2 D最后说一句，其实这个模型不用求什么最大还是最小值，只要得到一个满足所有constraints的feasible solution 就可以了，所以nobj的注释写的"anything"。