【转载】SUDOKU 游戏的GAMS 版本

huashi3483

随便发一个sudoku的gams代码。最主要的是请大家理解set 里面mapping 的写法。
5 J- f8 v3 [- i' N3 G3 k* Z/ [8 tSets  r  rows    / r1*r9 /
& c& }- B. n2 f3 b      c  columns / c1*c9 /
      b  blocks  / b1*b9 /
% Y& o' N' Z+ w  Z      v  values  / v1*v9 /
8 x# M( D. {" Q: ]; q      br(b,r)    /  b1*b3    .r1*r3,  b4*b6    .r4*r6,  b7*b9    .r7*r9 /
# Q5 I# c9 c3 y  V8 {  r      bc(b,c)    / (b1,b4,b7).c1*c3, (b2,b5,b8).c4*c6, (b3,b6,b9).c7*c9 /
5 p1 S8 k9 G, R( M$ _' N      brc(b,r,c) block definitions ;

brc(b,r,c) = br(b,r)*bc(b,c);
) N& y+ I/ M3 k+ S- k: v
Table problem(r,c) Hard problem with non-unique solution
! q7 G: f7 P* K8 w9 P7 ~/ T    c1   c2   c3   c4   c5   c6   c7   c8   c9
) J9 F( V( j" _$ \% I) ^7 P/ r1 ur1   2              6    7
r2            6                    2
  c5 ^6 c# E+ U, P: q" gr3   4                             8         1
' P) E+ h; b; }, Xr4   5                        9    3
: }3 v- W4 \( K3 S1 ]* a  Ar5        3                             5
r6             2    8                        7
r7             1
r8   7         8                   6
! D# V% b7 J( g1 W* B& Br9                       5    3              8 ;


Binary Variable X(r,c,v) assign value to cell (defined by row and column);
/ o7 e% _; X1 bVariable        W        objectiv value - anything;
5 F; m+ {0 u7 E* M& V, ?
; D1 O1 g" H; s# {1 D5 ~; `equations eq1(r,c) exactly one value for each cell
          eq2(c,v) column entries have to be unique
  o( o1 X7 a; P2 A6 \! z          eq3(r,v) row entries have to be unique
  D0 |: i) t0 R8 _5 G          eq4(b,v) block entries have to be unique
, l; \9 {# [4 J6 S  ^" v/ b          nobj     definition of objective - anything;

X.fx(r,c,v)$(problem(r,c)=ord(v)) = 1;
" q  t* Q. ]/ F1 J
eq1(r,c).. sum(v, X(r,c,v))          =E= 1;
8 ~' \% R7 Q" heq2(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));
  t) O/ R4 k8 }# `& [  P, ]
7 E+ U. k, G* amodel sudoku / all /;

; a' [3 K$ W: G! asolve sudoku minimizing w using mip;
' C6 H  s1 j% K' e最后说一句，其实这个模型不用求什么最大还是最小值，只要得到一个满足所有constraints的feasible solution 就可以了，所以nobj的注释写的"anything"。