《数独的难度分级》由会员分享，可在线阅读，更多相关《数独的难度分级（4页珍藏版）》请在金锄头文库上搜索。
1、数独的难度分级： 对于一个给定的数独，影响求解其难度的因素有很多，各种因素之间可能又有联系，根 据前文对数独的研究，我们认为主要的因素有：求解时间、空格数目、空格的分布情况、求 解办法。3.1 因素的分析1. 求解时间 对于给定的数独，难道越大，求解所花费的时间久越长，因此求解时间能够客观地 反映一个数独发难度程度。但是该衡量标准又有极限性，因为求解时间还受到所用求解 办法的影响，对同一个数独问题，不同的求解办法所花费的时间不一样，因此当比较两 个不同数独问题的求解时间时，还要考虑到它们所用到的求解办法；2. 空格数目在一般的情况下，数独的初始盘中所含有的空格数目越多，那么求解难度往往会越大，
2、但这种判定办法也不是绝对的，比如如下的两个数独问题：其中数独 1 有 53 个未知数，数独 2 有 52 个未知数，虽然数独 1 的空格数目比数独2 的空格数目多，但是明显数独1 的比数独2 简单的多，所以数独的难度还跟空格所在 的位置有关，即跟数独的初始盘中空格的分布情况有关；3. 空格的分布情况 由上面的分析可知，空格的分布情况对数独的难度影响极大，如下面的个数独初始 盘，虽然它们的空格数都为4，但是其分布情况不一样，导致数独4 比数独3 的难度大 很多；1儿A47 | 43 ! d 9588 i&沁d 532637219LS |58 | 7 |37 3 | 91 i 6 21应辽sfg
3、Ur3 ! 2 | 6 | 5 ! 19g他82 376j14 i T9 3 ! 6253数独 4数独 34. 求解办法 根据本论文的前面部分对数独的解法研究可知，数独的求解办法有很多种，其复杂 程度也不一样，对于一些比较复杂的数独问题，可能需要用比较复杂的求解办法，并且大部分会结合几种解法才能最终求出终盘。但是不同的人求解数独所利用的办法又大为 不同，因此采用求解办法来衡量数独的难度可能会产生不同的标准，具有极限性。3.2 建立难度衡量标准根据上面的因素分析，我们知道影响数独的最重要的因素是空格的分布情况，下面来分 析其原因，如下面两个数独的初始盘 ：1儿447 i 43 | d 95 j
4、6 | 88eKj 5fj rr i-17 2(8九皿L 4 58 | 7 |3L |2 I 9T i 1 9116 28呂E 51垃辽5 4F 3(53 ! 2 64 5 ! 19 a F9他82 1 3 | 76 | d 44 ! H 79 8百2532 7 j 43 U 95冷沱& 9临瓦打話325 6&4i 28L g i6 U 58 7|31 |2 97 | 3 1 91 ! &2S 1 1 5L 8 1 25冷订f 3術3百4 |9 8 |79 5 | 82 3 n6 k 44 U!?9 $ E2污站数独 3 数独 4 两个初始都含有4个空格，但分布不一样，其中数独3的初始盘中4
5、个空格的分布是独 立，即彼此的求解互不影响，我们可以很快地确定空格的数值为：a = 2 , a = 4, a = 4 ,112558a = 5。但是数独4的初始盘中4个空格的分布并不独立，空格a和空格a以及a和a8223243334分布在同一行中，它们的数值（候选数）的选择相互影响；空格a、a在同一列，空格23 33a、a同列，因此它们的取值会相互影响；空格a和a在同一个宫A中，空格a和243423331124a在同一个宫A中，在同一个宫中的空格之间数值的确定也会相互影响，因此可以得出3412结论：数独 4 比数独 3 的难度大。由上面的分析可知，空格的分布情况可以由空格之间的相关性来衡量，空
6、格之间具有相关性的数目越多，那么数独的难度就越大，因此我们可以建立下面的衡量标准：用九来表示空格a和a之间的相关性，即ij ,mnij mn1 , a与a相关九 =ijmn，ij,mn I 0 , a 与a 无关ij mnij mn那么ij mn其中，a和a相关有三种情况：a与a同行，a与a同列，a与a同宫。 ij mnij mn我们定义空格a的相关度函数为g 丿，其中， B 代表所有空格的集合。工九i,jBi, jB m,nBF(A)=-fS =丄工g6L丄工八2 x 9 x N 18 Nij18 Nij ,mni, jeBi, jeB m,nB为了避免空格的数目对相关性产生影响，以及考虑到每个空格的相关度的计算都重复了 一遍，为此我们对总难度程度进行修正，引入空格总数目N，修正后数独A的总难度程度 函数为：3.3 数独的难度分级根据所建立的衡量标准，容易证明： F（A） 1，利用这个衡量标准，我们将数独难度划分为4 个等级，如下表所示：难度分级表级别I级II级III级IV级F（A）00.250.25557.257.251利用上述分级标准，我们队论文第三部分所生成的100 道数独问题进行难度分级，得出难度分布如下：级别I级II级III级IV级数目那么九的具体取值情况如下:
