【转载】SUDOKU 游戏的GAMS 版本

huashi3483

随便发一个sudoku的gams代码。最主要的是请大家理解set 里面mapping 的写法。
Sets  r  rows    / r1*r9 /
, t7 k% v" P8 A2 X9 x8 ~      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 /
+ g8 ?# Y2 a3 q6 K) f0 ]& D& z      bc(b,c)    / (b1,b4,b7).c1*c3, (b2,b5,b8).c4*c6, (b3,b6,b9).c7*c9 /
      brc(b,r,c) block definitions ;

" U3 A# h- v4 P* j1 Ybrc(b,r,c) = br(b,r)*bc(b,c);
5 Z+ U1 f9 L1 W2 l) ^
- b: p4 L3 E/ G7 H  V( qTable problem(r,c) Hard problem with non-unique solution
1 x! k% g+ T' R    c1   c2   c3   c4   c5   c6   c7   c8   c9
1 L+ s/ |$ a' G0 Jr1   2              6    7
+ n, ?9 j0 U2 k0 u0 }' @! Qr2            6                    2
/ l% [: f8 Y6 M6 g1 |7 @r3   4                             8         1
2 C& _. q. z( l( J  Y6 z" Er4   5                        9    3
r5        3                             5
4 _& D$ O' w, _! V, Gr6             2    8                        7
r7             1
# a" a  R2 Y, O9 o6 R$ L, ^r8   7         8                   6
r9                       5    3              8 ;

6 d& z- t& V3 m; H. Y
Binary Variable X(r,c,v) assign value to cell (defined by row and column);
7 p0 R& z7 W# O) B* T2 s$ pVariable        W        objectiv value - anything;
2 h2 G$ _1 D4 A" F  ~; V# O/ z) d
equations eq1(r,c) exactly one value for each cell
          eq2(c,v) column entries have to be unique
4 @8 }" p3 k7 O          eq3(r,v) row entries have to be unique
          eq4(b,v) block entries have to be unique
9 g* o* E' a  q          nobj     definition of objective - anything;

- r% Z* I6 _: `/ EX.fx(r,c,v)$(problem(r,c)=ord(v)) = 1;

eq1(r,c).. sum(v, X(r,c,v))          =E= 1;
1 ?! l; `! V! J! b; U7 |1 A& Oeq2(c,v).. sum(r, X(r,c,v))          =E= 1;
eq3(r,v).. sum(c, X(r,c,v))          =E= 1;
7 z' Y; s! f! B: F: Aeq4(b,v).. sum(brc(b,r,c), X(r,c,v)) =E= 1;
nobj..     W =E= sum((r,c,v), X(r,c,v));
* G+ Q$ {$ j+ J. i5 K* B
, m% i- v1 z& N* y8 imodel sudoku / all /;
( w; J7 L# C/ C5 c8 @* q
solve sudoku minimizing w using mip;
最后说一句，其实这个模型不用求什么最大还是最小值，只要得到一个满足所有constraints的feasible solution 就可以了，所以nobj的注释写的"anything"。