【转载】SUDOKU 游戏的GAMS 版本

huashi3483

随便发一个sudoku的gams代码。最主要的是请大家理解set 里面mapping 的写法。
Sets  r  rows    / r1*r9 /
8 R9 X4 W1 P9 ]. e      c  columns / c1*c9 /
8 e  v! t) S; Z      b  blocks  / b1*b9 /
* P5 n0 Y4 B& e! ^/ T4 A      v  values  / v1*v9 /
      br(b,r)    /  b1*b3    .r1*r3,  b4*b6    .r4*r6,  b7*b9    .r7*r9 /
      bc(b,c)    / (b1,b4,b7).c1*c3, (b2,b5,b8).c4*c6, (b3,b6,b9).c7*c9 /
      brc(b,r,c) block definitions ;
: K2 ^, @0 H  a5 v2 f) {
brc(b,r,c) = br(b,r)*bc(b,c);
$ {/ ~3 M; u* r- c
Table problem(r,c) Hard problem with non-unique solution
4 `7 M# V7 f0 o$ y- `3 p    c1   c2   c3   c4   c5   c6   c7   c8   c9
2 s$ C# @/ M/ m' P, mr1   2              6    7
r2            6                    2
r3   4                             8         1
% T$ S6 P- Y( G% j$ y6 @3 Ar4   5                        9    3
r5        3                             5
, j, |6 y7 A1 x, ir6             2    8                        7
1 {% ]  P2 v5 U2 B/ a6 pr7             1
; m) @+ h  s, F3 Or8   7         8                   6
8 i4 p2 K0 q, N4 q2 f- Z4 D$ [r9                       5    3              8 ;
+ c6 o6 k4 h9 P3 _; W- W/ f: F

Binary Variable X(r,c,v) assign value to cell (defined by row and column);
+ I6 m" C4 h4 QVariable        W        objectiv value - anything;

; Z  y' H# f- k# N- W5 o2 I/ hequations eq1(r,c) exactly one value for each cell
5 i- e, U) W) b: ]: E' ]          eq2(c,v) column entries have to be unique
3 P; Y- A: N9 o. k          eq3(r,v) row entries have to be unique
8 g/ E0 i. t1 J3 ]$ ]          eq4(b,v) block entries have to be unique
          nobj     definition of objective - anything;
  ^* K% D0 S9 K4 y
X.fx(r,c,v)$(problem(r,c)=ord(v)) = 1;

eq1(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;
+ h5 l+ d- Z; i, v7 Neq4(b,v).. sum(brc(b,r,c), X(r,c,v)) =E= 1;
nobj..     W =E= sum((r,c,v), X(r,c,v));
7 T4 H/ D. J" M+ S1 w: s" d! C! }
: D% M" D0 y; Q" tmodel sudoku / all /;
$ A: Z. W0 t( c  L: t8 U' r# ~
solve sudoku minimizing w using mip;
5 E4 j$ e% v/ K% s/ {$ O最后说一句，其实这个模型不用求什么最大还是最小值，只要得到一个满足所有constraints的feasible solution 就可以了，所以nobj的注释写的"anything"。