数学建模社区-数学中国

标题: 数学中国2008美赛B题观点 [打印本页]

作者: madio 时间: 2008-2-16 10:52
标题: 数学中国2008美赛B题观点
虽然B题的源程序和相关书籍都可以在网上找到，但是本题的难度依然存在，主要在于如何制定一个衡量游戏难度的标准，书中提到的一种标准是依靠空白格子的数目来判断，而且提到只要空白格子的数目少于总数的一半的时候就可以保证有唯一解，但是这种做法恐怕不能得到太多的难度等级，所以这个地方还应该再考虑已经确定数字格子之间的距离以及数字之间的相互关系，特别是要从求解算法的角度出发，因为影响求解算法时间复杂度的主要因素是出现回溯的次数，也可以利用这个来构造难度等级。另外一个需要注意的地方就是要求生成游戏的算法必须有唯一解，这是一个很有趣的地方，书中谈到只要数字满足对称就可以保证唯一解，我们可以先生成一个具有对称数字的表格，再按照难度去掉其中的一些数字来生成数独游戏。另外一种做法是求解方法的反其道而行之，因为求解方法其实是一种分枝定界方法，出现多解的情况就是出现了多个分枝，我们可以尝试砍掉一些分枝，当然这需要你们对求解算法有一个深入地理解。最后一个当然是要尽量降低生成算法的复杂度，其实要实现这个要求最好的办法就是先生成游戏的解，再按照难度去掉一些数字，这和上面的保证唯一解的思路是一样的，就看你要怎样保证唯一解了！好了，就说这么多吧，希望你给您点帮助！

[此贴子已经被作者于2008-2-16 10:54:04编辑过]

作者: yongzlee 时间: 2008-2-16 11:25

有道理，难度等级是最难的部分了。难度等级必须得指引生成题目的算法。

作者: lipiji1986 时间: 2008-2-16 12:52
hehe

作者: jguo586 时间: 2008-2-16 14:56

老大，你提到

书中谈到只要数字满足对称就可以保证唯一解

的依据是那句话？是不是下面这句？

In addition to being symmetrical, Sudoku puzzles have another, often-debated “rule”: all
Sudoku puzzles must have one and only one solution. That is, no matter how you solve
the puzzle, the answer must ultimately be the same.

~~~~我感觉上面这段话不是这个意思~~不知道是不是我英语水平有限，理解错了~~

作者: bluefishly 时间: 2008-2-16 19:00

谢谢分享…………

作者: zswx 时间: 2009-1-21 13:40
现在看里还是那么难

作者: lovecan 时间: 2009-2-1 10:41
谢谢分享！

作者: captain87 时间: 2009-2-1 10:42
我当时想的就是制定四个难度等级是关键

但是后来还是选择了A题

作者: qingruo 时间: 2010-5-13 21:47
回复 1# madio
谢谢分享！

作者: zwt23232008 时间: 2010-5-14 10:47
好东西，谢谢楼主分享....

.............

作者: 杨帆 时间: 2010-8-14 14:06
谢谢分享。。。

作者: 杨帆 时间: 2010-8-14 14:07
谢谢分享。。。

欢迎光临数学建模社区-数学中国 (http://www.madio.net/)