数独的难度分级

数独的难度分级：对于一个给定的数独，影响求解其难度的因素有很多，各种因素之间可能又有联系，根据前文对数独的研究，我们认为主要的因素有：求解时间、空格数目、空格的分布情况、求解办法。3.1因素的分析1.求解时间对于给定的数独，难道越大，求解所花费的时间久越长，因此求解时间能够客观地反映一个数独发难度程度。但是该衡量标准又有极限性，因为求解时间还受到所用求解办法的影响，对同一个数独问题，不同的求解办法所花费的时间不一样，因此当比较两个不同数独问题的求解时间时，还要考虑到它们所用到的求解办法；2.空格数目在一般的情况下，数独的初始盘中所含有的空格数目越多，那么求解难度往往会越大，但这种判定办法也不是绝对的，比如如下的两个数独问题：数独1数独2其中数独1有53个未知数，数独2有52个未知数，虽然数独1的空格数目比数独2的空格数目多，但是明显数独1的比数独2简单的多，所以数独的难度还跟空格所在的位置有关，即跟数独的初始盘中空格的分布情况有关；3.空格的分布情况由上面的分析可知，空格的分布情况对数独的难度影响极大，如下面的个数独初始盘，虽然它们的空格数都为4，但是其分布情况不一样，导致数独4比数独3的难度大很多；数独3数独44.求解办法根据本论文的前面部分对数独的解法研究可知，数独的求解办法有很多种，其复杂程度也不一样，对于一些比较复杂的数独问题，可能需要用比较复杂的求解办法，并且大部分会结合几种解法才能最终求出终盘。但是不同的人求解数独所利用的办法又大为不同，因此采用求解办法来衡量数独的难度可能会产生不同的标准，具有极限性。3.2建立难度衡量标准根据上面的因素分析，我们知道影响数独的最重要的因素是空格的分布情况，下面来分析其原因，如下面两个数独的初始盘：数独3数独4两个初始都含有4个空格，但分布不一样，其中数独3的初始盘中4个空格的分布是独立，即彼此的求解互不影响，我们可以很快地确定空格的数值为：112a，254a，584a，825a。但是数独4的初始盘中4个空格的分布并不独立，空格23a和空格24a以及33a和34a分布在同一行中，它们的数值（候选数）的选择相互影响；空格2333aa、在同一列，空格2434aa、同列，因此它们的取值会相互影响；空格23a和33a在同一个宫11A中，空格24a和34a在同一个宫12A中，在同一个宫中的空格之间数值的确定也会相互影响，因此可以得出结论：数独4比数独3的难度大。由上面的分析可知，空格的分布情况可以由空格之间的相关性来衡量，空格之间具有相关性的数目越多，那么数独的难度就越大，因此我们可以建立下面的衡量标准：用,ijmn来表示空格ija和mna之间的相关性，即,1,=0,ijmnijmnijmnaaaa与相关与无关，其中，ija和mna相关有三种情况：①ijmnaa与同行,②ijmnaa与同列,③ijmnaa与同宫。我们定义空格ija的相关度函数为ijg，那么,,ijijmnmnBg，其中，B代表所有空格的集合。那么，我们可以得出数独A总相关度函数为：,,,,=ijijmnijBijBmnBfg为了避免空格的数目对相关性产生影响，以及考虑到每个空格的相关度的计算都重复了一遍，为此我们对总难度程度进行修正，引入空格总数目N，修正后数独A的总难度程度函数为：,,,,11==291818ijijmnijBijBmnBfFAgNNN3.3数独的难度分级根据所建立的衡量标准，容易证明：01FA，利用这个衡量标准，我们将数独难度划分为4个等级，如下表所示：难度分级表级别I级II级III级IV级FA0~0.250.25~55~7.257.25~1利用上述分级标准，我们队论文第三部分所生成的100道数独问题进行难度分级，得出难度分布如下：级别I级II级III级IV级数目那么,ijmn的具体取值情况如下：,ijmn1ijmnaa与同行ijmnaa与同列ijmnaa与同宫0其他