数独的难度分级

数独的难度分级：

对于一个给定的数独，影响求解其难度的因素有很多，各种因素之间可能又有联系，根据前文对数独的研究，我们认为主要的因素有：求解时间、空格数目、空格的分布情况、求解办法。

3.1 因素的分析

1.求解时间

对于给定的数独，难道越大，求解所花费的时间久越长，因此求解时间能够客观地反映一个数独发难度程度。但是该衡量标准又有极限性，因为求解时间还受到所用求解办法的影响，对同一个数独问题，不同的求解办法所花费的时间不一样，因此当比较两个不同数独问题的求解时间时，还要考虑到它们所用到的求解办法；

2.空格数目

在一般的情况下，数独的初始盘中所含有的空格数目越多，那么求解难度往往会越大，但这种判定办法也不是绝对的，比如如下的两个数独问题：

数独1 数独2

其中数独1有53个未知数，数独2有52个未知数，虽然数独1的空格数目比数独2的空格数目多，但是明显数独1的比数独2简单的多，所以数独的难度还跟空格所在的位置有关，即跟数独的初始盘中空格的分布情况有关；

3.空格的分布情况

由上面的分析可知，空格的分布情况对数独的难度影响极大，如下面的个数独初始盘，虽然它们的空格数都为4，但是其分布情况不一样，导致数独4比数独3的难度大很多；

数独3 数独4

4.求解办法

根据本论文的前面部分对数独的解法研究可知，数独的求解办法有很多种，其复杂程度也不一样，对于一些比较复杂的数独问题，可能需要用比较复杂的求解办法，并且

大部分会结合几种解法才能最终求出终盘。但是不同的人求解数独所利用的办法又大为不同，因此采用求解办法来衡量数独的难度可能会产生不同的标准，具有极限性。 3.2 建立难度衡量标准

根据上面的因素分析，我们知道影响数独的最重要的因素是空格的分布情况，下面来分析其原因，如下面两个数独的初始盘 ：

数独3 数独4 两个初始都含有4个空格，但分布不一样，其中数独3的初始盘中4个空格的分布是独立，即彼此的求解互不影响，我们可以很快地确定空格的数值为：112a =，254a =，584a =，825a =。

但是数独4的初始盘中4个空格的分布并不独立，空格23a 和空格24a 以及33a 和34a 分布在同一行中，它们的数值（候选数）的选择相互影响；空格2333a a 、在同一列，空格2434a a 、同列，因此它们的取值会相互影响；空格23a 和33a 在同一个宫11A 中，空格24a 和34a 在同一个宫12A 中，在同一个宫中的空格之间数值的确定也会相互影响，因此可以得出结论：数独4比数独3的难度大。

由上面的分析可知，空格的分布情况可以由空格之间的相关性来衡量，空格之间具有相关性的数目越多，那么数独的难度就越大，因此我们可以建立下面的衡量标准：

用,ij mn λ 来表示空格ij a 和mn a 之间的相关性，即

, 1 ,

=0 , ij mn ij mn ij mn a a a a λ?????

与相关与无关，

其中，ij a 和mn a 相关有三种情况：①ij mn a a 与同行,②ij mn a a 与同列,③ij mn a a 与同宫。

我们定义空格ij a 的相关度函数为()

ij g λ， 那么

(),,ij ij mn

m n B

g λλ∈

=

∑，

其中，B 代表所有空格的集合。那么，我们可以得出数独A 总相关度函数为：

()(),,,,=ij ij mn

i j B

i j B m n B

f g λλλ∈∈∈

=

∑∑∑

为了避免空格的数目对相关性产生影响，以及考虑到每个空格的相关度的计算都重复了

一遍，为此我们对总难度程度进行修正，引入空格总数目N ，修正后数独A 的总难度程度函数为：

()()(),,,,11

=

=291818ij ij mn i j B i j B m n B

f F A

g N N N λλλ∈∈∈=??∑∑∑

3.3 数独的难度分级

根据所建立的衡量标准，容易证明：()01F A ≤<

，利用这个衡量标准，我们将数独

难度划分为4个等级，如下表所示：

那么,ij mn λ的具体取值情况如下：