【转载】SUDOKU 游戏的GAMS 版本

huashi3483

随便发一个sudoku的gams代码。最主要的是请大家理解set 里面mapping 的写法。
Sets  r  rows    / r1*r9 /
      c  columns / c1*c9 /
6 X  @* _/ V: r, P2 j- U9 x      b  blocks  / b1*b9 /
* S8 S( x- S1 a/ {0 D1 I+ `! b  D& F      v  values  / v1*v9 /
5 w( n- q( |9 y% h* N      br(b,r)    /  b1*b3    .r1*r3,  b4*b6    .r4*r6,  b7*b9    .r7*r9 /
: f" a% V3 E6 J4 e1 G      bc(b,c)    / (b1,b4,b7).c1*c3, (b2,b5,b8).c4*c6, (b3,b6,b9).c7*c9 /
      brc(b,r,c) block definitions ;
* m2 W; X1 T: b: L1 H
" G0 y0 H3 ~) k) t  Pbrc(b,r,c) = br(b,r)*bc(b,c);
' O! ~! K  S% g; X0 M5 n8 ~" r
2 K" O* t/ D  |$ `* o1 X  Z( iTable problem(r,c) Hard problem with non-unique solution
    c1   c2   c3   c4   c5   c6   c7   c8   c9
r1   2              6    7
' ?, }3 X8 E) Y% ~0 Y8 Hr2            6                    2
r3   4                             8         1
0 P" H9 }6 p( H' Pr4   5                        9    3
; q. l% v. u% e# u" \+ Wr5        3                             5
r6             2    8                        7
r7             1
r8   7         8                   6
) S# G, w2 n, ~2 ~% J9 m2 Kr9                       5    3              8 ;

7 l) ?* N- b, U( C
7 Q2 P0 X- I2 z9 O! F. j6 B: `Binary Variable X(r,c,v) assign value to cell (defined by row and column);
- A" W) o( F1 q8 O+ G. U+ EVariable        W        objectiv value - anything;

equations eq1(r,c) exactly one value for each cell
4 b; y* Y3 t( f% M- {0 u          eq2(c,v) column entries have to be unique
- R; g: A3 ~% z6 }2 `) P          eq3(r,v) row entries have to be unique
# p% ~/ q. X+ ~1 }$ N          eq4(b,v) block entries have to be unique
          nobj     definition of objective - anything;
0 F* m" P2 F7 ?
X.fx(r,c,v)$(problem(r,c)=ord(v)) = 1;

eq1(r,c).. sum(v, X(r,c,v))          =E= 1;
eq2(c,v).. sum(r, X(r,c,v))          =E= 1;
. [9 R5 j1 m8 Oeq3(r,v).. sum(c, X(r,c,v))          =E= 1;
# Z% M( L1 c* T( L, H. s4 yeq4(b,v).. sum(brc(b,r,c), X(r,c,v)) =E= 1;
nobj..     W =E= sum((r,c,v), X(r,c,v));

model sudoku / all /;
* S4 l$ D% |' _7 r& w
solve sudoku minimizing w using mip;
最后说一句，其实这个模型不用求什么最大还是最小值，只要得到一个满足所有constraints的feasible solution 就可以了，所以nobj的注释写的"anything"。