数独的难度分级

1、-作者xxxx-日期xxxx数独的难度分级【精品文档】数独的难度分级：对于一个给定的数独，影响求解其难度的因素有很多，各种因素之间可能又有联系，根据前文对数独的研究，我们认为主要的因素有：求解时间、空格数目、空格的分布情况、求解办法。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的难度大。由上面的分析可知，空格的分布情况可以由空格之间的相关性来衡量，空格之间具有相关性的数目越多，那么数独的难度就越大，因此我们可以建立下面的衡量标准：用 来表示空格和之间的相关性，即 ，其中，和相关有三种情况：,。我们定义空格的相关度函数为， 那么，其中，代表所有空格的集合。那么，我们可以得出数独总相关度函数为：为了避免空格的数目对相关性产生影响，以及考虑到每个空格的相关度的计算都重复了一遍，为此我们对总难度程度进行修正，引入空格总数目，修正后数独的总难度程度函数为：3.3 数独的难度分级根据所建立的衡量标准，容易证明：，利用这个衡量标准，我们将数独难度划分为4个等级，如下表所示： 难度分级表级别I级II级III级IV级0.2557.251利用上述分级标准，我们队论文第