【转载】SUDOKU 游戏的GAMS 版本

huashi3483

随便发一个sudoku的gams代码。最主要的是请大家理解set 里面mapping 的写法。
Sets  r  rows    / r1*r9 /
      c  columns / c1*c9 /
# h( P8 M1 }# p: G  z  U) ^      b  blocks  / b1*b9 /
# g0 D* H6 E, @5 E2 Z      v  values  / v1*v9 /
( \% ]3 W/ ^# R      br(b,r)    /  b1*b3    .r1*r3,  b4*b6    .r4*r6,  b7*b9    .r7*r9 /
1 \8 z+ I1 q( u( E% b0 t2 }      bc(b,c)    / (b1,b4,b7).c1*c3, (b2,b5,b8).c4*c6, (b3,b6,b9).c7*c9 /
" i5 C+ e  |/ A# E% \1 h      brc(b,r,c) block definitions ;

9 A+ P6 a" [- v: u. o. u" ibrc(b,r,c) = br(b,r)*bc(b,c);
9 ~" l) H! L0 `* n
Table problem(r,c) Hard problem with non-unique solution
    c1   c2   c3   c4   c5   c6   c7   c8   c9
r1   2              6    7
9 C& U# c. Z- {- \: g0 |# ]r2            6                    2
# J: D8 C) |4 f9 u6 N& C  O4 {r3   4                             8         1
" G% p2 {4 u3 m/ Wr4   5                        9    3
& \$ y3 Z7 g  X( mr5        3                             5
r6             2    8                        7
4 D: j: Y, K$ I4 x( j3 J' gr7             1
' Q% u4 g0 o. r, b  Gr8   7         8                   6
r9                       5    3              8 ;
8 n; N8 e* Z0 T1 s; w# F
) b7 T8 ~3 x5 w6 ]& i* E
Binary Variable X(r,c,v) assign value to cell (defined by row and column);
) A9 y1 i6 i) O$ x. dVariable        W        objectiv value - anything;

6 @1 Z2 }' K4 H9 |8 f/ j3 Iequations eq1(r,c) exactly one value for each cell
          eq2(c,v) column entries have to be unique
/ v% L2 F- E9 t! H2 O. @          eq3(r,v) row entries have to be unique
, ?1 y/ f/ }  F! x2 B( i: @          eq4(b,v) block entries have to be unique
+ ?7 o: O) [9 N# D, C- T/ p          nobj     definition of objective - anything;
0 Q8 r& ?1 z4 Q" |9 D$ I
X.fx(r,c,v)$(problem(r,c)=ord(v)) = 1;

eq1(r,c).. sum(v, X(r,c,v))          =E= 1;
# |$ {9 L0 p3 I9 ]9 C4 m9 Oeq2(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;
  M1 \9 k$ V- R1 M! Z: t0 \nobj..     W =E= sum((r,c,v), X(r,c,v));
3 O: `: b* C3 ~: ]: J
4 r% B- [7 Q/ K+ G& Omodel sudoku / all /;
2 z3 w0 R7 l8 s( Z8 C: G0 y
solve sudoku minimizing w using mip;
! ]+ ^7 V' Z3 H& t2 u7 O; x最后说一句，其实这个模型不用求什么最大还是最小值，只要得到一个满足所有constraints的feasible solution 就可以了，所以nobj的注释写的"anything"。