【转载】SUDOKU 游戏的GAMS 版本

[复制链接]

字体大小: 正常放大

huashi3483

1253 主题	442 听众	-586 积分

复兴中华数学头子

TA的每日心情

	开心 2011-9-26 17:31

签到天数: 3 天

[LV.2]偶尔看看I

自我介绍: 数学中国网站（www.madio.cn）是目前中国最大的数学建模交流社区

群组: 越狱吧

群组: 湖南工业大学数学建模同盟会

群组: 四川农业大学数学建模协会

群组: 重庆交通大学数学建模协会

群组: 中国矿业大学数学建模协会

电梯直达

1^#

发表于 2009-11-14 05:19 |只看该作者 |正序浏览

|招呼Ta 关注Ta |邮箱已经成功绑定

随便发一个sudoku的gams代码。最主要的是请大家理解set 里面mapping 的写法。
Sets  r  rows / r1*r9 /
   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 /
   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);

Table problem(r,c) Hard problem with non-unique solution
c1 c2 c3 c4 c5 c6 c7 c8 c9
r1 2             6 7
r2          6                   2
r3 4                            8       1
r4 5                      9 3
r5       3                            5
r6          2 8                      7
r7          1
r8 7       8                6
r9                      5 3             8 ;

Binary Variable X(r,c,v) assign value to cell (defined by row and column);
Variable       W       objectiv value - anything;

equations eq1(r,c) exactly one value for each cell
      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
      nobj    definition of objective - anything;

X.fx(r,c,v)$(problem(r,c)=ord(v)) = 1;

eq1(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));

model sudoku / all /;

solve sudoku minimizing w using mip;
最后说一句，其实这个模型不用求什么最大还是最小值，只要得到一个满足所有constraints的feasible solution 就可以了，所以nobj的注释写的"anything"。

zan