【转载】SUDOKU 游戏的GAMS 版本

huashi3483

随便发一个sudoku的gams代码。最主要的是请大家理解set 里面mapping 的写法。
Sets  r  rows    / r1*r9 /
      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 /
0 v' n* _+ g8 w/ z9 h. w  l1 }      bc(b,c)    / (b1,b4,b7).c1*c3, (b2,b5,b8).c4*c6, (b3,b6,b9).c7*c9 /
& k$ j/ s8 y5 [0 I' g$ w      brc(b,r,c) block definitions ;

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

! f, t, ?* O' x4 ^1 b$ m& J# BTable problem(r,c) Hard problem with non-unique solution
    c1   c2   c3   c4   c5   c6   c7   c8   c9
/ Q+ B% Y: I, ir1   2              6    7
r2            6                    2
r3   4                             8         1
7 j" H& K( `3 ?+ @5 g* V7 D9 h$ Wr4   5                        9    3
, {7 o# D9 \) c2 ?& @+ m* {r5        3                             5
r6             2    8                        7
- C4 s/ |, `- i* ^( J, G; R6 Cr7             1
% V. h1 x7 ^3 u: J- x9 Vr8   7         8                   6
8 i! J9 p  [& {" \: j1 w. [- z$ H! fr9                       5    3              8 ;
( F9 E4 O1 x% [5 [
7 V1 r! H* i, z2 C
Binary Variable X(r,c,v) assign value to cell (defined by row and column);
Variable        W        objectiv value - anything;

. s- \, h7 g( o- U- ~. U' N2 wequations eq1(r,c) exactly one value for each cell
          eq2(c,v) column entries have to be unique
% _6 z9 M/ R6 |- m  X" \          eq3(r,v) row entries have to be unique
          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;
# k" s& k- X1 C* F1 b+ S$ v
eq1(r,c).. sum(v, X(r,c,v))          =E= 1;
$ h- L5 U6 c1 B: weq2(c,v).. sum(r, X(r,c,v))          =E= 1;
eq3(r,v).. sum(c, X(r,c,v))          =E= 1;
1 e" s$ M. c3 |+ m& `* z( oeq4(b,v).. sum(brc(b,r,c), X(r,c,v)) =E= 1;
nobj..     W =E= sum((r,c,v), X(r,c,v));

+ ?  i, c5 s# @6 f* b) d8 Qmodel sudoku / all /;

solve sudoku minimizing w using mip;
) v, M/ X3 P  b+ U( b; L最后说一句，其实这个模型不用求什么最大还是最小值，只要得到一个满足所有constraints的feasible solution 就可以了，所以nobj的注释写的"anything"。