【转载】SUDOKU 游戏的GAMS 版本

huashi3483

随便发一个sudoku的gams代码。最主要的是请大家理解set 里面mapping 的写法。
$ B1 N% D$ K2 wSets  r  rows    / r1*r9 /
      c  columns / c1*c9 /
. u5 J6 v6 w0 z& [7 n      b  blocks  / b1*b9 /
3 w; K# l' P  L( V+ i      v  values  / v1*v9 /
      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 /
      brc(b,r,c) block definitions ;
) G4 l6 z1 ]) Y
* s) d: M' A' r7 q0 ^& F% Tbrc(b,r,c) = br(b,r)*bc(b,c);

Table problem(r,c) Hard problem with non-unique solution
( F5 Y/ R* y6 Z/ @    c1   c2   c3   c4   c5   c6   c7   c8   c9
r1   2              6    7
r2            6                    2
r3   4                             8         1
! Q- C+ w1 q; w9 p. {+ xr4   5                        9    3
r5        3                             5
r6             2    8                        7
r7             1
r8   7         8                   6
r9                       5    3              8 ;


1 r- q! N% h3 i6 ~) QBinary Variable X(r,c,v) assign value to cell (defined by row and column);
1 ~' r4 K, n% G% ]5 IVariable        W        objectiv value - anything;
) l4 j( n) F+ y9 b
equations eq1(r,c) exactly one value for each cell
) o( `. c' {% G; @          eq2(c,v) column entries have to be unique
( A  w& G3 @. I: k" s. o          eq3(r,v) row entries have to be unique
! R2 K, ?0 V6 U3 N: @; @* k/ V          eq4(b,v) block entries have to be unique
8 I7 }) P* |2 X+ }; ]          nobj     definition of objective - anything;
; A5 o' Q1 T) u$ L9 t- l
9 |3 R7 k/ n2 n9 F  w5 kX.fx(r,c,v)$(problem(r,c)=ord(v)) = 1;

eq1(r,c).. sum(v, X(r,c,v))          =E= 1;
" W5 Z( a! U& Q/ Keq2(c,v).. sum(r, X(r,c,v))          =E= 1;
eq3(r,v).. sum(c, X(r,c,v))          =E= 1;
/ I# `* o6 u$ g& deq4(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 w# l1 V& o8 Mmodel sudoku / all /;

, a( [2 E4 g6 V2 S( d6 K, ^: `9 ^solve sudoku minimizing w using mip;
最后说一句，其实这个模型不用求什么最大还是最小值，只要得到一个满足所有constraints的feasible solution 就可以了，所以nobj的注释写的"anything"。