【转载】SUDOKU 游戏的GAMS 版本

huashi3483

随便发一个sudoku的gams代码。最主要的是请大家理解set 里面mapping 的写法。
Sets  r  rows    / r1*r9 /
      c  columns / c1*c9 /
9 y. ]9 O+ r, v. l      b  blocks  / b1*b9 /
      v  values  / v1*v9 /
2 S& f( I- r9 I) n) w: y- K2 T      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 /
8 N9 [4 e/ K) V/ F7 p5 `6 ^      brc(b,r,c) block definitions ;

brc(b,r,c) = br(b,r)*bc(b,c);

, U$ {  {+ @  ^8 `Table problem(r,c) Hard problem with non-unique solution
5 u# N4 s* x, ]+ G: _* o; J7 I' s5 J2 R    c1   c2   c3   c4   c5   c6   c7   c8   c9
$ r( ?5 P; l9 G3 W( [r1   2              6    7
r2            6                    2
r3   4                             8         1
r4   5                        9    3
. s1 P6 q7 [# ~- w) @) |, U# @r5        3                             5
r6             2    8                        7
7 X3 v% H% G8 k' A9 ^1 P0 Q/ [$ Gr7             1
r8   7         8                   6
: G, V8 t, i$ \$ P) d4 i( Vr9                       5    3              8 ;


( v2 ]# P' p, HBinary Variable X(r,c,v) assign value to cell (defined by row and column);
Variable        W        objectiv value - anything;
4 ~1 a* }; |& j/ v' j" V- i+ l
equations eq1(r,c) exactly one value for each cell
          eq2(c,v) column entries have to be unique
( G) x, ]$ w) {+ H, ]) I          eq3(r,v) row entries have to be unique
- U3 x, [8 P$ z& ^1 x& ?' L          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;
, B) _% g. [3 c8 b7 N9 M
. ~* Y$ @7 }9 m/ q, Y0 c) ieq1(r,c).. sum(v, X(r,c,v))          =E= 1;
4 q+ n% Q; G; W+ j. D* ?) seq2(c,v).. sum(r, X(r,c,v))          =E= 1;
4 G  |. E( N: P: p2 Qeq3(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));
& V) d4 j2 O# V& d* U" M
model sudoku / all /;
  d# H" x$ N) M( `. s: B4 i
6 ]6 K) e% [  d: osolve sudoku minimizing w using mip;
6 B! \( z- F3 L" k6 K; |最后说一句，其实这个模型不用求什么最大还是最小值，只要得到一个满足所有constraints的feasible solution 就可以了，所以nobj的注释写的"anything"。