【转载】SUDOKU 游戏的GAMS 版本

huashi3483

随便发一个sudoku的gams代码。最主要的是请大家理解set 里面mapping 的写法。
+ l0 i. P( X1 w$ D" @3 n$ ySets  r  rows    / r1*r9 /
, V: U3 u/ M* H  X6 C4 C: a! \      c  columns / c1*c9 /
      b  blocks  / b1*b9 /
: ?0 U5 w5 {# Y% [      v  values  / v1*v9 /
8 \8 Z' }( ~4 I& a: j/ ]      br(b,r)    /  b1*b3    .r1*r3,  b4*b6    .r4*r6,  b7*b9    .r7*r9 /
      bc(b,c)    / (b1,b4,b7).c1*c3, (b2,b5,b8).c4*c6, (b3,b6,b9).c7*c9 /
1 o/ X! o# P0 D3 |0 e! l      brc(b,r,c) block definitions ;

8 n. n# Y4 b: X: ?5 k. vbrc(b,r,c) = br(b,r)*bc(b,c);

" c4 l* Y2 r5 j3 |4 n, [1 uTable problem(r,c) Hard problem with non-unique solution
    c1   c2   c3   c4   c5   c6   c7   c8   c9
r1   2              6    7
& I# |% ?' U3 L, G: R) Z1 }r2            6                    2
. c  `. _( G( h5 zr3   4                             8         1
2 T) ~- E0 T6 f' Ar4   5                        9    3
r5        3                             5
& x. N" ?8 d) G7 z( l# S# `r6             2    8                        7
$ [# r. W1 z" s- v3 @- {r7             1
8 M, h8 p# t- Gr8   7         8                   6
! W" U- d: r9 a5 N! Q5 S! L. ?r9                       5    3              8 ;


2 o/ L: r* t4 R+ rBinary Variable X(r,c,v) assign value to cell (defined by row and column);
$ b* {% s% ~# O9 AVariable        W        objectiv value - anything;

equations eq1(r,c) exactly one value for each cell
          eq2(c,v) column entries have to be unique
# R& T6 H5 ~& g' b; H- E: [          eq3(r,v) row entries have to be unique
: N  R, m6 ~* I0 m9 B          eq4(b,v) block entries have to be unique
5 ^! Y; F+ ^; F5 l# @          nobj     definition of objective - anything;

X.fx(r,c,v)$(problem(r,c)=ord(v)) = 1;
' L7 c5 y" f& g2 m+ K
5 J: p/ Z% G* J2 P; ~& r0 {! m# H: qeq1(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));

model sudoku / all /;
) X! w% p! r' {3 d, \$ K, T7 e
solve sudoku minimizing w using mip;
, U) s4 T7 _3 A3 h. }% Y最后说一句，其实这个模型不用求什么最大还是最小值，只要得到一个满足所有constraints的feasible solution 就可以了，所以nobj的注释写的"anything"。