【转载】SUDOKU 游戏的GAMS 版本

huashi3483

随便发一个sudoku的gams代码。最主要的是请大家理解set 里面mapping 的写法。
7 U$ Z$ n) r, x' X9 tSets  r  rows    / r1*r9 /
7 r* Z8 N+ k; h% O+ L. z      c  columns / c1*c9 /
      b  blocks  / b1*b9 /
& L% k: J9 ]9 Z$ f; s      v  values  / v1*v9 /
  j% v3 G+ a4 z+ r  R5 A3 d      br(b,r)    /  b1*b3    .r1*r3,  b4*b6    .r4*r6,  b7*b9    .r7*r9 /
' }$ a8 ~6 s! }* d, P. ^9 a; B6 W      bc(b,c)    / (b1,b4,b7).c1*c3, (b2,b5,b8).c4*c6, (b3,b6,b9).c7*c9 /
6 Q( @) x7 P5 H; _4 [      brc(b,r,c) block definitions ;

* `1 ]( \' v9 wbrc(b,r,c) = br(b,r)*bc(b,c);
$ }" R$ Q: n& E: U
2 E: `" D1 Y7 q  I1 W0 ^1 MTable problem(r,c) Hard problem with non-unique solution
    c1   c2   c3   c4   c5   c6   c7   c8   c9
r1   2              6    7
r2            6                    2
, j' }5 ?3 C9 P, nr3   4                             8         1
! N, _9 Z. i3 l7 n$ n5 nr4   5                        9    3
, w: @, f+ A: Or5        3                             5
& [) N: O5 V& k- P+ [r6             2    8                        7
9 r: [/ F* h. ~. p9 sr7             1
r8   7         8                   6
. U& I" I# D9 {3 _- Yr9                       5    3              8 ;
9 p( Z% I+ K6 ]4 _9 @; P

6 F  R  G7 W0 [! I% _Binary Variable X(r,c,v) assign value to cell (defined by row and column);
Variable        W        objectiv value - anything;

% [) }7 Y8 Z1 R* Q- @. b; p6 P  Nequations 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
$ x9 ~9 `$ d* E! E# Q          eq4(b,v) block entries have to be unique
          nobj     definition of objective - anything;
9 U- }- y6 |6 R2 s% Y
0 _( B/ ^' f  {+ a9 |% p- ?$ i6 GX.fx(r,c,v)$(problem(r,c)=ord(v)) = 1;

! E- N: A9 g* @8 m8 V; oeq1(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 I- V$ z. |' E3 J2 r  Req4(b,v).. sum(brc(b,r,c), X(r,c,v)) =E= 1;
nobj..     W =E= sum((r,c,v), X(r,c,v));

/ [% F+ x2 K7 W; z7 _model sudoku / all /;

solve sudoku minimizing w using mip;
  l# d6 J# L, u" Y5 B最后说一句，其实这个模型不用求什么最大还是最小值，只要得到一个满足所有constraints的feasible solution 就可以了，所以nobj的注释写的"anything"。