数独的难度分级

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

2、判定办法也不是绝对的，比如如下的两个数独问题：310.9.060,4卫一0：2 o070008000000260,06000S0431：00q0 ! 5 妙oio0?2 40.030 iJj0：0 1数独1数独2其中数独1有33个未知数，数独2有32个未知数，虽然数独1的空格数U 比数独2的空格数LI多，但是明显数独1的比数独2简单的多，所以数独的难度还 跟空格所在的位置有关，即跟数独的初始盘中空格的分布情况有关；3. 空格的分布情况山上面的分析可知，空格的分布悄况对数独的难度影响极大，如下面的个数 独初始盘，虽然它们的空格数都为4,但是其分布惜况不一样，导致数独4比数独 3的难度大很多；i1

3、14.44an 8 釘.112 bL69(128致518244356849372691894153981827365269S48264b5.L.1ii3；li9诗q 空28567L数独4数独34. 求解办法根据本论文的前面部分对数独的解法研究可知，数独的求解办法有很多种， 其复杂程度也不一样，对于一些比较复杂的数独问题，可能需要用比较复杂的求解 办法，并且大部分会结合儿种解法才能最终求出终盘。但是不同的人求解数独所利 用的办法乂大为不同，因此釆用求解办法来衡量数独的难度可能会产生不同的标 准，具有极限性。3. 2建立难度衡量标准根据上面的因素分析，我们知道影响数独的最逼要的因素是空格的分布情

4、况，下面来分析其原因，如下面两个数独的初始盘：如7 1 4 8 9 7 i 2 i 83j7|4 i 9 j 6H7 3II 1 !s2I95III 6X - 98in3 i 2 ! 儿9 % 4 i 14.8425 ! 6 h：2 ! 84 i 916,4158j7|31,2.947 h baJaU.s h isL | 8 ! 25 9 47|36364j5l9!SI44411179!8l62,53数独3数独4两个初始都含有4个空格，但分布不一样，其中数独3的初始盘中4个空格的分布是独立，即彼此的求解互不影响，我们可以很快地确定空格的数值为： 如=2 吆=499=5。但是数独4的初始盘中4个

5、空格的分布并不独立，空格和空格以及和 “34分布在同一行中，它们的数值（候选数）的选择相互影响；空格 陶、轴在同一列，空格“24、“34同列，因此它们的取值会相互影响；空格和 在同一个宫中，空格 和在同一个宫中，在同一个宫中的空格之间数值的确定也会相互影响，因此可以得岀结论：数独 4比数独3的难度大。山上面的分析可知，空格的分布情况可以山空格之间的相关性来衡量，空格之间具有相关性的数LI越多，那么数独的难度就越大，因此我们可以建立下面的衡 量标准：用来表示空格和之间的相关性，即其中，和相关有三种情况:勺与硯司列我们定义空格的相关度函数为M,那么g二工坷严其中，B代表所有空格的集合。那么，我们可以得出数独A总相关度函数为：/二工貞易卜工E佥为了避免空格的数LI对相关性产生影响，以及考虑到每个空格的相关度的汁 算都重复了一遍，为此我们对总难度程度进行修正，引入空格总数口N,修正后数独A的总难度程度函数为：（仃而占w而展3. 3数独的难度分级根据所建立的衡量标准，容易证明:0F（A）,利用这个衡量标准，我们将数独难度划分为4个等级，如下表所示:难度分级表级别I级II级III级IV级尸）00. 250. 25557. 257. 251利用上述分级标准