【转载】SUDOKU 游戏的GAMS 版本

huashi3483

随便发一个sudoku的gams代码。最主要的是请大家理解set 里面mapping 的写法。
) R- Z$ x: l, pSets  r  rows    / r1*r9 /
      c  columns / c1*c9 /
( `, I3 a& X% w( o' |: J+ W+ F      b  blocks  / b1*b9 /
      v  values  / v1*v9 /
0 ^$ s* h9 \; M& ^      br(b,r)    /  b1*b3    .r1*r3,  b4*b6    .r4*r6,  b7*b9    .r7*r9 /
  D; l, S7 k  \( D) q      bc(b,c)    / (b1,b4,b7).c1*c3, (b2,b5,b8).c4*c6, (b3,b6,b9).c7*c9 /
      brc(b,r,c) block definitions ;
7 O+ P# E+ |4 I/ L; A7 c
brc(b,r,c) = br(b,r)*bc(b,c);

0 e( r1 [  V+ ]) a' A9 _* uTable problem(r,c) Hard problem with non-unique solution
2 X1 ~9 k8 x  ^2 g    c1   c2   c3   c4   c5   c6   c7   c8   c9
r1   2              6    7
r2            6                    2
  E8 D7 R+ Y$ t; M0 U- _3 Ir3   4                             8         1
1 X$ ~$ ^: e5 D4 c# Z' w& lr4   5                        9    3
: O3 o" K% b. p+ M" ur5        3                             5
8 u! B: I' w! Qr6             2    8                        7
r7             1
* ^0 l9 t0 I+ x2 x& ^2 p/ cr8   7         8                   6
* e5 e1 n7 H2 H* B& {r9                       5    3              8 ;
4 @6 ]5 Z% p1 ]6 g2 ~, m) J
- M; r4 E; y4 h1 h( k8 p0 Z
Binary Variable X(r,c,v) assign value to cell (defined by row and column);
Variable        W        objectiv value - anything;

' j6 K" B, I! Z/ R' p$ bequations eq1(r,c) exactly one value for each cell
          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
3 f0 s" m5 D+ I1 ^4 m, {          nobj     definition of objective - anything;

6 {# I1 \9 m2 Y8 sX.fx(r,c,v)$(problem(r,c)=ord(v)) = 1;

# E# a7 P6 S2 f& t+ h2 Eeq1(r,c).. sum(v, X(r,c,v))          =E= 1;
1 M  L8 S0 Z7 Weq2(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;
nobj..     W =E= sum((r,c,v), X(r,c,v));
! B: Z/ u4 X5 `6 W! d2 I) P* H# [
model sudoku / all /;

1 {, d8 @' C! N6 U. `2 Q  fsolve sudoku minimizing w using mip;
最后说一句，其实这个模型不用求什么最大还是最小值，只要得到一个满足所有constraints的feasible solution 就可以了，所以nobj的注释写的"anything"。