【转载】SUDOKU 游戏的GAMS 版本

huashi3483

随便发一个sudoku的gams代码。最主要的是请大家理解set 里面mapping 的写法。
Sets  r  rows    / r1*r9 /
9 U' t4 _" Q0 B) q$ ]: ?# R. F      c  columns / c1*c9 /
3 q- b+ W( ~: E  |) C% }- ^) e      b  blocks  / b1*b9 /
      v  values  / v1*v9 /
      br(b,r)    /  b1*b3    .r1*r3,  b4*b6    .r4*r6,  b7*b9    .r7*r9 /
# w! I2 F, R, X3 u; l" h! G2 A6 `      bc(b,c)    / (b1,b4,b7).c1*c3, (b2,b5,b8).c4*c6, (b3,b6,b9).c7*c9 /
) n8 h/ l( d7 m& i' d) ^      brc(b,r,c) block definitions ;

; U0 w' z% l/ R6 W2 R4 [& Y9 }brc(b,r,c) = br(b,r)*bc(b,c);

' z- c  k! W4 ?: fTable problem(r,c) Hard problem with non-unique solution
    c1   c2   c3   c4   c5   c6   c7   c8   c9
. ?+ x( R3 L, Q9 p; r1 Wr1   2              6    7
# K$ r7 I  t4 S$ D3 b+ C: S2 c/ kr2            6                    2
, s: x3 l3 o9 i0 e- K- rr3   4                             8         1
r4   5                        9    3
; z: G: M1 F4 ]  T* ~% E0 Zr5        3                             5
r6             2    8                        7
, k' V$ N  G4 `' fr7             1
" F# R& }; R  `0 ^: o" ^( hr8   7         8                   6
r9                       5    3              8 ;

9 @, {0 h$ k6 W, ]  o  q
Binary Variable X(r,c,v) assign value to cell (defined by row and column);
6 F0 @  N6 m7 s% C& _+ pVariable        W        objectiv value - anything;
2 Y' \7 @* Q2 l: p
equations eq1(r,c) exactly one value for each cell
          eq2(c,v) column entries have to be unique
: R' x  j( ]1 u          eq3(r,v) row entries have to be unique
          eq4(b,v) block entries have to be unique
          nobj     definition of objective - anything;
! w4 N8 Z( a+ @( W& ^
X.fx(r,c,v)$(problem(r,c)=ord(v)) = 1;

7 B5 M! j' a8 ]4 g, Deq1(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;
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));

( ?' J! }+ Q# f! J7 f6 `model sudoku / all /;

solve sudoku minimizing w using mip;
% t* F0 B! V% B6 _4 b2 J+ ^最后说一句，其实这个模型不用求什么最大还是最小值，只要得到一个满足所有constraints的feasible solution 就可以了，所以nobj的注释写的"anything"。