12 / 2 页下一页

查看: 7152|回复: 11

数学中国2008美赛B题观点

[复制链接]

字体大小: 正常放大

madio

3万主题	1312 听众	5万积分

TA的每日心情

	奋斗 2024-7-1 22:21

签到天数: 2014 天

[LV.Master]伴坛终老

自我介绍: 数学中国站长

群组: 数学建模培训课堂1

群组: 数学中国美赛辅助报名

群组: Matlab讨论组

群组: 2013认证赛A题讨论群组

群组: 2013认证赛C题讨论群组

电梯直达

1^#

发表于 2008-2-16 10:52 |只看该作者 |倒序浏览

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

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

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

zan

转播0 淘帖0 分享0 收藏0 支持1 反对0 微信

数学建模社会化

使用道具举报

yongzlee

0 主题	3 听众	14 积分

升级 9.47%

该用户从未签到

2^#

发表于 2008-2-16 11:25 |只看该作者 |招呼Ta 关注Ta

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

我也说一句

发表

使用道具举报

lipiji1986

7 主题	3 听众	68 积分

升级 66.32%

该用户从未签到

3^#

发表于 2008-2-16 12:52 |只看该作者 |招呼Ta 关注Ta

hehe

我也说一句

发表

使用道具举报

jguo586

1 主题	3 听众	42 积分

升级 38.95%

该用户从未签到

4^#

发表于 2008-2-16 14:56 |只看该作者 |招呼Ta 关注Ta

老大，你提到

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

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

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.

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