正文

数独的难度评价2007-01-26 14:46:00

【评论】 【打印】 【字体: 】 本文链接:http://blog.pfan.cn/rickone/22828.html

分享到:

随便说几句,刚从网上找了一下一些比较难的CASE,似乎用计算机做也是‘口算’得到结果,于是我就想,看来我还是真不懂数独,数独毕竟是人玩的,要按游戏规则出牌。于是我就想如何评价一个数独的难度,以让人可以接受,因为人在玩游戏的时候是需要信心的,由易到难是一般做法。

数独的难度不好评价,因为它的各种局面互不相关,你别想用一种方法解决所有数独,这也是它的魅力所在,有人爱玩数独,因为他上瘾了,真的欲罢不能。

数独的推理性强,像一些数学思想,推理,假设,反证(找矛盾)都有影子,换成计算机,它也做类似的事情,推理和假设变成搜索,反证变成回溯,做一件数学工作,难度就体现在这些基本的工作重复了多少,越多越难,如果推两下就出结果,那就容易,所以……

就一般性的数独难度,拿两个指标来衡量,搜索次数S和回溯次数T,T越大越难,但和S也有关系,应该描述成回溯率,比如同样是回溯了10次,一个是20次的搜索,另一个是80次的搜索,那难度应该不同。换个思路,T可以看成是无效搜索,它一定是S的一子集,即T<=S,如果T=S就表示无解,回退到了一开始的情况,而难度应该和有效搜索有关系,有效搜索比率就定义为难度系数,即H=(S-T)/S,它是[0,1]内的小数,它越小越难,那对一个难度的评价,可以取它的倒数,或者负对数,怎么表示好,看实验情况。

其它因素。科学的评价,应该要考虑其它因素,像空格数,做为初学者就会觉得很重要,还有各个空格的不确定度,但是这些因素都会或多或少的影响到S和T。这里评价的前提是按照同样的搜索算法,那个算法和不确定度有关系,所以也可以反映出来。

总结出来,评价的具体方法是,运用偶的搜索算法试解一个数独,在调用dfs时S计数加一,在dfs退出时T计数加一,在搜索到第一个解时停止统计,计算H,给出S,T和H。

阅读(8389) | 评论(5)


版权声明:编程爱好者网站为此博客服务提供商,如本文牵涉到版权问题,编程爱好者网站不承担相关责任,如有版权问题请直接与本文作者联系解决。谢谢!

评论

loading...
您需要登录后才能评论,请 登录 或者 注册