【转载】SUDOKU 游戏的GAMS 版本

huashi3483

随便发一个sudoku的gams代码。最主要的是请大家理解set 里面mapping 的写法。
Sets  r  rows    / r1*r9 /
+ K3 h2 r5 t" j- u$ b2 I" G      c  columns / c1*c9 /
      b  blocks  / b1*b9 /
  N6 D* w# J7 d$ y( k  s- B$ l% @      v  values  / v1*v9 /
1 ?1 t2 K: J, O      br(b,r)    /  b1*b3    .r1*r3,  b4*b6    .r4*r6,  b7*b9    .r7*r9 /
( E7 C; O  [) G- o, j      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);
5 `( T: j# S: ~( g! |- R( ~7 p
Table problem(r,c) Hard problem with non-unique solution
$ d1 k6 N1 B% O* k    c1   c2   c3   c4   c5   c6   c7   c8   c9
* M( p0 }1 ?+ p0 i# r- }r1   2              6    7
r2            6                    2
1 o) R: c) b5 y+ dr3   4                             8         1
1 u5 T$ x: b* l9 q0 B4 k7 b4 @( Dr4   5                        9    3
( c/ A. n- Y" Wr5        3                             5
r6             2    8                        7
r7             1
  T9 Y# j$ k- F9 `7 Ur8   7         8                   6
' i/ B. r4 O- V* J% G& D: [9 vr9                       5    3              8 ;


Binary Variable X(r,c,v) assign value to cell (defined by row and column);
Variable        W        objectiv value - anything;
: x# S* \* @3 G& Y$ I, q- G( D; \
equations 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
          nobj     definition of objective - anything;
: X) Y" k; m5 S' M& j8 w* k
/ I. q# l, P0 sX.fx(r,c,v)$(problem(r,c)=ord(v)) = 1;

0 w1 N# S& G* c1 ceq1(r,c).. sum(v, X(r,c,v))          =E= 1;
eq2(c,v).. sum(r, X(r,c,v))          =E= 1;
1 p" P! I7 D1 ?3 g. o/ `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;
2 S3 }+ z3 C3 w* h3 o7 Inobj..     W =E= sum((r,c,v), X(r,c,v));
' o7 `- k# T" H2 E8 o1 h6 ^8 F  S1 I
% N! V1 ^. t! S* y% l* ^model sudoku / all /;

: X- V! U' L8 F. d& T1 A  \solve sudoku minimizing w using mip;
5 K( x" S5 ?$ u最后说一句，其实这个模型不用求什么最大还是最小值，只要得到一个满足所有constraints的feasible solution 就可以了，所以nobj的注释写的"anything"。