数独的难度分级

《数独的难度分级》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数独的难度分级：对于一个给定的数独，影响求解其难度的因素有很多，各种因素之间可能又有联系，根据前文对数独的研究，我们认为主要的因素有：求解时间、空格数目、空格的分布情况、求解办法。3.1因素的分析1.求解时间对于给定的数独，难道越大，求解所花费的时间久越长，因此求解时间能够客观地反映一个数独发难度程度。但是该衡量标准又有极限性，因为求解时间还受到所用求解办法的影响，对同一个数独问题，不同的求解办法所花费的时间不一样，因此当比较两个不同数独问题的求解时间时，还要考虑到它们所用到的求解办法；2.空格数目在一般的情况

2、下，数独的初始盘中所含有的空格数目越多，那么求解难度往往会越大，但这种判定办法也不是绝对的，比如如下的两个数独问题：数独1数独2其中数独1有53个未知数，数独2有52个未知数，虽然数独1的空格数目比数独2的空格数目多，但是明显数独1的比数独2简单的多，所以数独的难度还跟空格所在的位置有关，即跟数独的初始盘中空格的分布情况有关；3.空格的分布情况由上面的分析可知，空格的分布情况对数独的难度影响极大，如下面的个数独初始盘，虽然它们的空格数都为4，但是其分布情况不一样，导致数独4比数独3的难度大很多；数独3数独44.

3、求解办法根据本论文的前面部分对数独的解法研究可知，数独的求解办法有很多种，其复杂程度也不一样，对于一些比较复杂的数独问题，可能需要用比较复杂的求解办法，并且大部分会结合几种解法才能最终求出终盘。但是不同的人求解数独所利用的办法又大为不同，因此采用求解办法来衡量数独的难度可能会产生不同的标准，具有极限性。3.2建立难度衡量标准根据上面的因素分析，我们知道影响数独的最重要的因素是空格的分布情况，下面来分析其原因，如下面两个数独的初始盘：数独3数独4两个初始都含有4个空格，但分布不一样，其中数独3的初始盘中4个空格的

4、分布是独立，即彼此的求解互不影响，我们可以很快地确定空格的数值为：，，，。但是数独4的初始盘中4个空格的分布并不独立，空格和空格以及和分布在同一行中，它们的数值（候选数）的选择相互影响；空格在同一列，空格同列，因此它们的取值会相互影响；空格和在同一个宫中，空格和在同一个宫中，在同一个宫中的空格之间数值的确定也会相互影响，因此可以得出结论：数独4比数独3的难度大。由上面的分析可知，空格的分布情况可以由空格之间的相关性来衡量，空格之间具有相关性的数目越多，那么数独的难度就越大，因此我们可以建立下面的衡量标准：用来表

5、示空格和之间的相关性，即，其中，和相关有三种情况：①,②,③。我们定义空格的相关度函数为，那么，其中，代表所有空格的集合。那么，我们可以得出数独总相关度函数为：为了避免空格的数目对相关性产生影响，以及考虑到每个空格的相关度的计算都重复了一遍，为此我们对总难度程度进行修正，引入空格总数目，修正后数独的总难度程度函数为：3.3数独的难度分级根据所建立的衡量标准，容易证明：，利用这个衡量标准，我们将数独难度划分为4个等级，如下表所示：难度分级表级别I级II级III级IV级0~0.250.25~55~7.257.25~

6、1利用上述分级标准，我们队论文第三部分所生成的100道数独问题进行难度分级，得出难度分布如下：级别I级II级III级IV级数目那么的具体取值情况如下：10其他