【转载】SUDOKU 游戏的GAMS 版本

huashi3483

随便发一个sudoku的gams代码。最主要的是请大家理解set 里面mapping 的写法。
- Y0 N& ]- }" ]" H& r% XSets  r  rows    / r1*r9 /
      c  columns / c1*c9 /
* u6 ~( b& K$ Q$ T6 s1 {      b  blocks  / b1*b9 /
0 G  f9 C& }6 Z' W% X. T      v  values  / v1*v9 /
/ Z8 `8 h% D/ ?; p      br(b,r)    /  b1*b3    .r1*r3,  b4*b6    .r4*r6,  b7*b9    .r7*r9 /
) o( a8 l5 ~. p      bc(b,c)    / (b1,b4,b7).c1*c3, (b2,b5,b8).c4*c6, (b3,b6,b9).c7*c9 /
# q2 @7 Y2 X2 B  x; ?7 P      brc(b,r,c) block definitions ;

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

Table problem(r,c) Hard problem with non-unique solution
, Q" G, z1 F" T/ _    c1   c2   c3   c4   c5   c6   c7   c8   c9
" N2 a* x. h3 [; t3 y/ Wr1   2              6    7
r2            6                    2
5 s- _& k- J$ or3   4                             8         1
/ n; x' f. O: }r4   5                        9    3
% ^' U$ y/ \% R8 m- T* ~: A# `/ sr5        3                             5
r6             2    8                        7
! q1 t0 D/ i6 ]! f$ I% {: t# c6 b4 d. Rr7             1
5 ?5 i: D' e& g4 y2 `; t. ~, X, }r8   7         8                   6
r9                       5    3              8 ;


Binary Variable X(r,c,v) assign value to cell (defined by row and column);
Variable        W        objectiv value - anything;

; ?$ ~1 O# C* `+ Nequations eq1(r,c) exactly one value for each cell
          eq2(c,v) column entries have to be unique
6 x) M2 H) Q1 y1 N7 E. U2 z( ~- Y" R2 Z          eq3(r,v) row entries have to be unique
          eq4(b,v) block entries have to be unique
          nobj     definition of objective - anything;
3 v" Z! c) m: N1 p  X  \
X.fx(r,c,v)$(problem(r,c)=ord(v)) = 1;

7 d. C$ J% ^* y; q/ S' K% Geq1(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;
3 L8 h1 r1 N$ T8 c/ O) Meq4(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 /;
# F3 f) Y3 m9 j3 b+ G, d9 s1 Y
solve sudoku minimizing w using mip;
最后说一句，其实这个模型不用求什么最大还是最小值，只要得到一个满足所有constraints的feasible solution 就可以了，所以nobj的注释写的"anything"。