随便说几句，刚从网上找了一下一些比较难的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。

评论