数学建模社区-数学中国

标题: 【转载】SUDOKU 游戏的GAMS 版本 [打印本页]

作者: huashi3483    时间: 2009-11-14 05:19
标题: 【转载】SUDOKU 游戏的GAMS 版本
随便发一个sudoku的gams代码。最主要的是请大家理解set 里面mapping 的写法。
; m- ?7 }6 Y4 I$ _& [7 B8 u$ E0 USets  r  rows    / r1*r9 /
- l: v# ^, Y8 \8 a$ Q      c  columns / c1*c9 /
- K& E" a. R& h* U& {  c6 w      b  blocks  / b1*b9 /
5 Y0 z" M% {5 ^# A      v  values  / v1*v9 /5 q& V9 M8 P5 m
      br(b,r)    /  b1*b3    .r1*r3,  b4*b6    .r4*r6,  b7*b9    .r7*r9 /6 G; r, K4 M1 E- L- Q7 A- j
      bc(b,c)    / (b1,b4,b7).c1*c3, (b2,b5,b8).c4*c6, (b3,b6,b9).c7*c9 /
0 @" x& G, B5 K6 {& y5 d      brc(b,r,c) block definitions ;
/ T* t& H% B# A( z
. I+ j7 V1 ]. _) @, hbrc(b,r,c) = br(b,r)*bc(b,c);$ S: o! A; I. e3 w4 D
( U) N' s& R3 f2 b  l7 L5 `: b
Table problem(r,c) Hard problem with non-unique solution
% o% e2 U7 E" G% H! a6 a, X    c1   c2   c3   c4   c5   c6   c7   c8   c9
3 t) k! C# D2 Q, R# I: ~, Y* vr1   2              6    78 P0 N. f0 t- {; m
r2            6                    2
9 i& N6 K  }; _$ ~2 J; i0 gr3   4                             8         18 T$ z3 V+ f2 S+ I* r2 |3 F
r4   5                        9    32 n. z+ z! P+ n( j' f5 @
r5        3                             57 N: M1 a8 u. K! M- K) r
r6             2    8                        7" Y" j8 M6 l# `: A
r7             11 P1 Y, R* R; u* N5 \" y# v7 u
r8   7         8                   61 G0 w' p. k. U
r9                       5    3              8 ;; \  C3 }$ A  |- u! ?5 c# o9 Q7 f
7 G6 h9 {; E! i, D/ d/ T( f
( V  R4 n# Z: ]2 Q
Binary Variable X(r,c,v) assign value to cell (defined by row and column);8 R  ^" I1 L4 \
Variable        W        objectiv value - anything;
! S; `+ i0 W8 G2 @+ H- Q* j( z+ m! [% \. J" g! U8 _$ s
equations eq1(r,c) exactly one value for each cell: m, L* L: T8 z! {( z% x
          eq2(c,v) column entries have to be unique
/ {4 \$ L& q0 M% q          eq3(r,v) row entries have to be unique
! }8 p, `3 T& P1 n          eq4(b,v) block entries have to be unique  O% P  z+ D9 x; h
          nobj     definition of objective - anything;+ P; W+ j* O" Q
5 q2 R" E. ?! M, ^+ u7 P1 W% m
X.fx(r,c,v)$(problem(r,c)=ord(v)) = 1;
. y8 Z; d- ?1 O" p
+ L6 Z% B- |% J3 h/ ^- q% xeq1(r,c).. sum(v, X(r,c,v))          =E= 1;) `* K0 C9 \1 [; f
eq2(c,v).. sum(r, X(r,c,v))          =E= 1;+ }/ a& ^+ ^1 n8 x) Q
eq3(r,v).. sum(c, X(r,c,v))          =E= 1;* I: w9 e& O' y- D0 y: {- W1 J
eq4(b,v).. sum(brc(b,r,c), X(r,c,v)) =E= 1;4 _, _# v( C; S. l
nobj..     W =E= sum((r,c,v), X(r,c,v));. R9 p- d- M! j9 b: F& k( s
/ h5 c: R2 K3 }8 ~1 G9 s4 x# F
model sudoku / all /;
8 i# I) P+ O1 P$ x# q& Z' q' {; d1 C: `. K# Q
solve sudoku minimizing w using mip;8 ]5 i. Z7 t. W% R# \
最后说一句,其实这个模型不用求什么最大还是最小值,只要得到一个满足所有constraints的feasible solution 就可以了,所以nobj的注释写的"anything"。




欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5