【转载】SUDOKU 游戏的GAMS 版本

huashi3483

随便发一个sudoku的gams代码。最主要的是请大家理解set 里面mapping 的写法。
Sets  r  rows    / r1*r9 /
% p! W- R5 S  b8 Y2 o      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 /
) J0 y9 }  m5 Z) P" t) d8 l* M7 ?      bc(b,c)    / (b1,b4,b7).c1*c3, (b2,b5,b8).c4*c6, (b3,b6,b9).c7*c9 /
      brc(b,r,c) block definitions ;

brc(b,r,c) = br(b,r)*bc(b,c);
% y  V  \8 R& N2 g
& Q9 J2 x6 [4 W: d8 P- l* ETable problem(r,c) Hard problem with non-unique solution
6 {* ^. F0 T* {8 g    c1   c2   c3   c4   c5   c6   c7   c8   c9
. d9 V7 ], u+ [! ]' Cr1   2              6    7
0 e! ^3 X$ [* m9 hr2            6                    2
8 t0 m# N6 h3 p9 {+ Qr3   4                             8         1
: `9 ~+ c; a+ m1 e2 jr4   5                        9    3
8 M7 N' S$ w! r  T- H3 t/ ]3 N0 A9 vr5        3                             5
* ~; t' [, p. R7 J4 n! h7 Xr6             2    8                        7
# g$ \: f) F4 n" O! Y  a6 Qr7             1
: R. |3 ~7 T$ E2 e6 u  hr8   7         8                   6
r9                       5    3              8 ;
* m- Q# Y; A0 g8 C  E$ L5 v' p
& c4 a- R7 ~% s3 P0 D
3 }% h; {3 f5 A7 F9 QBinary Variable X(r,c,v) assign value to cell (defined by row and column);
Variable        W        objectiv value - anything;
+ v$ s: X4 I& O0 {; z! b2 Z
' d4 L4 R+ y: t$ sequations eq1(r,c) exactly one value for each cell
6 O! Z% N/ e# Y5 m3 Z6 j9 N          eq2(c,v) column entries have to be unique
          eq3(r,v) row entries have to be unique
, ~9 z" o4 ?' q& A, f          eq4(b,v) block entries have to be unique
" c! P3 h4 h, C1 J: ~0 b# J          nobj     definition of objective - anything;

X.fx(r,c,v)$(problem(r,c)=ord(v)) = 1;
, G$ H% s3 x* o4 B8 |
6 ~5 K" p# r8 u2 Jeq1(r,c).. sum(v, X(r,c,v))          =E= 1;
/ k% ~. }; R4 C* P- H! s+ \- jeq2(c,v).. sum(r, X(r,c,v))          =E= 1;
7 L+ e; k; H; T. p! A7 aeq3(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));
5 F; Q0 ~& L$ S6 c# C% e1 W# V2 f
* y4 K- _+ {3 ~: s( X) `4 Tmodel sudoku / all /;
% q7 t( ~9 ~' L6 ~& v3 h# S1 H7 h# Q
4 y. M5 h, ]& r9 ]solve sudoku minimizing w using mip;
最后说一句，其实这个模型不用求什么最大还是最小值，只要得到一个满足所有constraints的feasible solution 就可以了，所以nobj的注释写的"anything"。