【转载】SUDOKU 游戏的GAMS 版本

huashi3483

随便发一个sudoku的gams代码。最主要的是请大家理解set 里面mapping 的写法。
Sets  r  rows    / r1*r9 /
      c  columns / c1*c9 /
  H4 q; J8 F2 W* b: S+ k) \; T      b  blocks  / b1*b9 /
2 d1 w4 D& s% ?      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 /
" i0 A" ~+ |2 D4 I      brc(b,r,c) block definitions ;

brc(b,r,c) = br(b,r)*bc(b,c);
2 A, \: m0 Y$ T2 o# x/ s
# O" P& b& t+ s+ E0 Q( `Table problem(r,c) Hard problem with non-unique solution
    c1   c2   c3   c4   c5   c6   c7   c8   c9
r1   2              6    7
' F- ~9 f1 u% p7 Z& kr2            6                    2
/ F2 C( y# Y' tr3   4                             8         1
r4   5                        9    3
r5        3                             5
r6             2    8                        7
: d, s2 q4 Q; Y# i, P9 Dr7             1
+ `$ i" K" l! u9 b2 O, S- Yr8   7         8                   6
" J- a9 r  `  v" |" gr9                       5    3              8 ;

: a8 K+ {3 [, U' \6 W
Binary Variable X(r,c,v) assign value to cell (defined by row and column);
Variable        W        objectiv value - anything;
' G1 |8 G0 X: f% R# J1 h
! j" S) Y2 N$ U6 ^( Y" \equations eq1(r,c) exactly one value for each cell
( S6 S5 C; f* y3 P          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
, |1 m3 N0 r, |          nobj     definition of objective - anything;
) ]# v; \$ e8 `
% }+ F' e' {) R$ U5 I+ H! vX.fx(r,c,v)$(problem(r,c)=ord(v)) = 1;

! t- o+ ~9 Z* G+ ~8 [eq1(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;
# h# h5 o& j( \2 E7 Jnobj..     W =E= sum((r,c,v), X(r,c,v));
1 N- Z; h& ^% c% |" O7 @
0 [& Y+ Z* B- _4 a$ z8 bmodel sudoku / all /;
/ m4 Q2 Q) }3 C" u/ @0 [+ D8 t  L% s
solve sudoku minimizing w using mip;
( S9 m0 H4 r# Z( g+ S3 Z最后说一句，其实这个模型不用求什么最大还是最小值，只要得到一个满足所有constraints的feasible solution 就可以了，所以nobj的注释写的"anything"。