【转载】SUDOKU 游戏的GAMS 版本

huashi3483

随便发一个sudoku的gams代码。最主要的是请大家理解set 里面mapping 的写法。
0 h0 T' E) j9 r4 FSets  r  rows    / r1*r9 /
& W9 E& r8 z% Q! o3 P7 z0 J- Q8 @      c  columns / c1*c9 /
      b  blocks  / b1*b9 /
: M1 @6 F  L# U9 Q# O      v  values  / v1*v9 /
! D+ |- Y: G* r      br(b,r)    /  b1*b3    .r1*r3,  b4*b6    .r4*r6,  b7*b9    .r7*r9 /
; g5 n/ v) a' d0 Q, u      bc(b,c)    / (b1,b4,b7).c1*c3, (b2,b5,b8).c4*c6, (b3,b6,b9).c7*c9 /
: \5 J, P8 U* A4 ]) Q      brc(b,r,c) block definitions ;
* `- c, V$ w: N7 n. {# o5 R. @' |
brc(b,r,c) = br(b,r)*bc(b,c);

8 [. @# H- ?$ l8 r* KTable problem(r,c) Hard problem with non-unique solution
    c1   c2   c3   c4   c5   c6   c7   c8   c9
r1   2              6    7
+ L4 V% F" _, G0 J; m( qr2            6                    2
r3   4                             8         1
r4   5                        9    3
8 l3 @2 x: d% p% j% B" tr5        3                             5
* T; f$ N6 k& O3 ~r6             2    8                        7
r7             1
+ q* r, `. A. u( U& ^) Dr8   7         8                   6
r9                       5    3              8 ;
7 L7 i& G! b& o* t: ^; c1 r9 s
9 S+ \! N. _3 i  G3 g7 o3 }! M
+ m# [: }" K8 P0 Z! xBinary Variable X(r,c,v) assign value to cell (defined by row and column);
Variable        W        objectiv value - anything;
1 l( G6 b' a1 N3 G
: E' S: |) f7 f& \& eequations eq1(r,c) exactly one value for each cell
, `7 }+ N, G* {" Y5 {          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
/ R) ~% o8 _$ Z: E2 I2 T+ e          nobj     definition of objective - anything;
& L- e% H/ ~3 p5 c
  z6 d) D( ?. Q; J+ \X.fx(r,c,v)$(problem(r,c)=ord(v)) = 1;

" n, h8 o; S% N) v4 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));
2 T/ U" \3 z' D6 S
( N$ Z5 \- z" f. n! ?5 @! j8 Emodel sudoku / all /;
5 n4 ^) u- y+ {
4 [: Z# `8 ?$ c) q  L2 wsolve sudoku minimizing w using mip;
最后说一句，其实这个模型不用求什么最大还是最小值，只要得到一个满足所有constraints的feasible solution 就可以了，所以nobj的注释写的"anything"。