【转载】SUDOKU 游戏的GAMS 版本

huashi3483

随便发一个sudoku的gams代码。最主要的是请大家理解set 里面mapping 的写法。
) }+ k& K. g7 ]- L: }: Y" QSets  r  rows    / r1*r9 /
7 G6 p/ r  M( M0 ?/ w- d      c  columns / c1*c9 /
      b  blocks  / b1*b9 /
      v  values  / v1*v9 /
      br(b,r)    /  b1*b3    .r1*r3,  b4*b6    .r4*r6,  b7*b9    .r7*r9 /
- z9 F# ~* }0 |4 y% Q% d" T4 ^      bc(b,c)    / (b1,b4,b7).c1*c3, (b2,b5,b8).c4*c6, (b3,b6,b9).c7*c9 /
      brc(b,r,c) block definitions ;
' ~- p! s5 y; R* }
5 k# `2 v9 {# O5 P& n+ x9 T! n' r8 ubrc(b,r,c) = br(b,r)*bc(b,c);
6 f" a8 |5 t8 v% j; I( D; K; c
Table problem(r,c) Hard problem with non-unique solution
    c1   c2   c3   c4   c5   c6   c7   c8   c9
! H: U- I$ L- `/ N/ E* {/ c2 _4 g9 m4 Ar1   2              6    7
r2            6                    2
3 N. G% W0 e# o2 j6 \( ]$ L( J1 N5 Pr3   4                             8         1
7 b7 K: k. e8 H8 O: @7 Xr4   5                        9    3
. A4 o% d2 n! l( N2 m# K2 }) G5 ar5        3                             5
r6             2    8                        7
7 S! ]* N, ^$ hr7             1
% `4 u( c; h. M9 u3 d9 m* o1 r* Ar8   7         8                   6
r9                       5    3              8 ;
: X5 S2 _& ^3 s* L% _) s2 [' C
# j2 p: b. _( R! H5 {
Binary Variable X(r,c,v) assign value to cell (defined by row and column);
Variable        W        objectiv value - anything;
0 K$ _2 A' N0 `4 o1 {
  i6 {6 X2 s* Z. p* Y( Aequations eq1(r,c) exactly one value for each cell
          eq2(c,v) column entries have to be unique
* [6 T+ O- l; i6 T' Z          eq3(r,v) row entries have to be unique
          eq4(b,v) block entries have to be unique
8 G* p! J6 J/ q5 r$ _3 \          nobj     definition of objective - anything;

X.fx(r,c,v)$(problem(r,c)=ord(v)) = 1;
# q7 o3 U  X, H3 `2 A9 J6 m. n
: q& k/ @& Y4 r( S8 `, leq1(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;
% k  U7 d1 h: B% G0 |! R- y+ Feq4(b,v).. sum(brc(b,r,c), X(r,c,v)) =E= 1;
; g& s( a- p, v+ _nobj..     W =E= sum((r,c,v), X(r,c,v));
# n- ]% h0 {4 A! W' f+ J2 [8 K
" _6 Y/ U% W7 W- a2 x% jmodel sudoku / all /;

solve sudoku minimizing w using mip;
5 X$ a2 H0 D8 U) Q最后说一句，其实这个模型不用求什么最大还是最小值，只要得到一个满足所有constraints的feasible solution 就可以了，所以nobj的注释写的"anything"。