【转载】SUDOKU 游戏的GAMS 版本

huashi3483

随便发一个sudoku的gams代码。最主要的是请大家理解set 里面mapping 的写法。
Sets  r  rows    / r1*r9 /
      c  columns / c1*c9 /
      b  blocks  / b1*b9 /
      v  values  / v1*v9 /
1 D0 L+ K; D5 E5 I      br(b,r)    /  b1*b3    .r1*r3,  b4*b6    .r4*r6,  b7*b9    .r7*r9 /
! _: D6 ?* ?, @2 @      bc(b,c)    / (b1,b4,b7).c1*c3, (b2,b5,b8).c4*c6, (b3,b6,b9).c7*c9 /
      brc(b,r,c) block definitions ;

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

# \- h# R' W( d( P1 b3 A& GTable problem(r,c) Hard problem with non-unique solution
    c1   c2   c3   c4   c5   c6   c7   c8   c9
r1   2              6    7
* P0 i% p+ T% E; L( I2 M. N  fr2            6                    2
r3   4                             8         1
r4   5                        9    3
r5        3                             5
r6             2    8                        7
r7             1
  k/ `5 V  y+ ^4 Mr8   7         8                   6
r9                       5    3              8 ;
0 |, f/ n/ \' E  A7 `1 m

Binary Variable X(r,c,v) assign value to cell (defined by row and column);
- L# W* H6 v/ h, @Variable        W        objectiv value - anything;

' {) U4 A, F' B1 f/ u! Uequations 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
8 p, Q2 _. f- w          eq4(b,v) block entries have to be unique
) X. q  [' @5 J          nobj     definition of objective - anything;
( l  e; k' A/ K3 t
X.fx(r,c,v)$(problem(r,c)=ord(v)) = 1;

1 ~4 h  v/ W8 q: G! j$ eeq1(r,c).. sum(v, X(r,c,v))          =E= 1;
eq2(c,v).. sum(r, X(r,c,v))          =E= 1;
5 z- I1 y6 ?4 `$ a2 Neq3(r,v).. sum(c, X(r,c,v))          =E= 1;
eq4(b,v).. sum(brc(b,r,c), X(r,c,v)) =E= 1;
# u9 `$ ~+ |! i3 ~nobj..     W =E= sum((r,c,v), X(r,c,v));

6 @( e, [' L! B3 B! E8 [7 Vmodel sudoku / all /;

! z: Z5 K/ n3 v# M! T) vsolve sudoku minimizing w using mip;
最后说一句，其实这个模型不用求什么最大还是最小值，只要得到一个满足所有constraints的feasible solution 就可以了，所以nobj的注释写的"anything"。