数独谜题难度级别划分的步数法研究

程 曦，肖华勇

（西北工业大学 理学院，陕西 西安 710129）

数独谜题游戏中，玩家面前放置了一个9×9格子的棋盘，这个棋盘分成了9个3×3的区域。这81个单元格当中有些格子一开始就填上了1-9之间的数字，当满足下面规则时，且有唯一的方法填满剩下的格子：每个格子包含一个1-9之间的数字且每一行、列和和3×3的区域包含集合{1，2，…，9}中数字一次。

一个数独谜题通过给定的一定格子的数字，通过这些初始数字确保能产生的唯一填满数字的棋盘，把填满数字的棋盘称为解决数独谜题的一种解题方法。数独谜题游戏的目标是通过初始给定的格子中数字，找出唯一的解题方法。

现阶段，对数独的研究主要在它的解答算法、生成算法，目前对数独的研究大部分集中在数独的解法上，比如文献[1]中的使用有限递归预处理求解数独谜题，文献[2]中的回溯候选数法求解数独，文献[3]中的枚举算法求解数独，文献[4]中的几何粒子群算法求解数独；文献[5]主要是对数独的生成算法进行了研究与讨论。

而对于数独谜题的难度划分，目前非常缺乏这方面的研究。我们尝试通过玩家经常使用的数独策略的角度来讨论划分数独谜题难度级别的方法，首先介绍常用的数独谜题策略。

1 常用数独谜题策略

把一个单元格的行号、列号及3×3区域号组合在一起称为这个格子的群组。两个以上的单元格若在同一行同一个3×3区域或同一列同一个3×3区域那么我们称这两个单元格在同一个群组。对任意一个未填入数字的单元格，将所有已经填入其所在行、列、3×3区域的数字排除，剩下的数字的集合称为该单元格的候选数集合。给定一个数独棋盘中一个单元格（i，j），其中 i代表它的行号，j代表它的列号，定义 S（i，j）为它的候选数集合。标号如图1所示。

图1 数独谜题的标号Fig.1 Sudoku puzzle’s mark

为了解决一个数独谜题，玩家能够使用很多策略以及很多逻辑上的删减法[6]，假定每个格子的候选数集合在使用策略前已经通过谜题当中的给定的初始数字初始化好了。

策略 1：显性唯一候选数法，如果一个单元格（i，j），它的候选数集合只有一个可能的数字，那么直接将这个候选数字填入空格；

策略2：隐性唯一候选数法，这个策略在一个给定的单元格（i，j）中以下条件可以使用：S（i，j）包含值 k 且（i，j）所在的群组中其他的格子的候选数集合并不包含值k。

策略3：显性对数候选数法，这个策略能在2个同群组单元格（i1，j1）、（i2，j2）且这 2 个单元格的候选数集 S（i1，j1）、S（i2，j2）有且只有2个相同的数字k1、k2中使用，那么就能将这个群组的其他单元格候选数集中这2个数字k1、k2全部删减掉。

策略4：隐性对数候选数法，这个策略在两个给定的同群组单元格（i1，j1）、（i2，j2）中以下条件可以使用： S（i1，j1）、S（i2，j2）均包含数字 k1、k2且（i1，j1）、（i2，j2）所在的群组中其他的单元格的候选数集合并不包含数字k1、k2，那么可以将除了k1，k2之外的数字在候选数集 S（i1，j1）、S（i2，j2）中排除。

策略 5：交叉排除法，若两个空格或3个空格在同一个群组中（比如同行同3×3区域或同列同3×3区域），若在某一个3×3区域中，若所有可能的数字都出现在同一行/列时，就可以把这个数字从该行/列的其他单元格中的候选数集合中删除或者在某一行/列中，当所有可能的数字都出现在同一个3×3区域中时，就可以把这个数字从该3×3区域其他单元格候选数集合中删除。

策略6：显性三数集候选数法，这个策略的使用情况如下：在 3 个单元格（i1，j1）、（i2，j2）、（i3，j3）（在同一个群组）且这 3个单元格的候选数集有且仅有3个数字k1、k2、k3，那么就能将这个群组的其他单元格候选数集中这3个数字k1、k2、k3全部删减掉。

策略 7：隐性三数集候选数法，这个策略在3个给定的同群组单元格（i1，j1）、（i2，j2）、（i3，j3）中以下条件可以使用 S（i1，j1）、S（i2，j2）、S（i3，j3）包含数字 k1、k2、k3且（i1，j1）、（i2，j2）、（i3，j3）所在的群组中其他的单元格的候选数集合并不包含数字k1、k2、k3，那么可以将除了 k1、k2、k3之外的数字在候选数集 S（i1，j1）、S（i2，j2）、S（i3，j3）中排除。

策略8：二链数删减法，若一个值正好出现且只出现在某两行的相同的两列上，则这个数字就可以从这两列上其他的单元格的候选数中删除。 若一个值k正好出现且只出现在某两列的相同的两行上，则这个数字就可以从这两行上的其他单元格的候选数中删除。

策略 9：显性四数集候选数法，这个策略使用情况如下：在 4 个同群组单元格（i1，j1）、（i2，j2）、（i3，j3）、（i4，j4）且这 4 个单元格的候选数集有且只有4个数字k1、k2、k3、k4，那么就能将这个群组的其他单元格候选数集中这4个数字 k1、k2、k3、k4全部删减掉。

策略 10：隐性四数集候选数法，这个策略在4个给定的同群组单元格（i1，j1）、（i2，j2）、（i3，j3）、（i4，j4）中以下条件可以使用 S（i1，j1）、S（i2，j2）、S（i3，j3）、S（i4，j4）包含数字 k1、k2、k3、k4且（i1，j1）、（i2，j2）、（i3，j3）、（i4，j4） 所在的群组中其他的单元格的候选数集合并不包含数字 k1、k2、k3、k4， 那么可以将除了 k1、k2、k3、k4之外的数字在候选数集 S（i1，j1）、S（i2，j2）、S（i3，j3）、S（i4，j4）中排除。

策略 11：XY形态匹配法，若XY和YZ同在一个3×3区域但不同行（列）中，而XZ和XY在同一行（列），但在不同3×3区域中.那么在XY所在区块中与XY所在行（列）交集空格中应该删除候选数Z，并且在XZ所在区块与YZ所在行（列）交集的空格中应该删除候选数Z。（其中XY，YZ，XZ分别是三空格的候选数，并且这三空格没有其他候选数）

策略 12：XYZ形态匹配法，若某3×3区域某空格候选数为XYZ，在该同3×3区域但不同列（行）的某空格候选数为YZ，且与XYZ所在空格同列（行）但不同3×3区域某空格候选数为XZ，那么XYZ所在3×3区域与 XZ所在列（行）的交集中的空格候选数不能为Z。

策略 13：三链数删减法，如果某个数字k在某3列（行）中只出现在相同的3行（列）中，则将从这3行（列）上其他的候选数中删除。

策略 14：WXYZ形态匹配法，若某3×3区域某空格候选数为WXYZ，在该同3×3区域但不同列（行）的某空格候选数为WZ，且与WXYZ所在空格同列（行）但不同3×3区域某两个空格候选数为 XZ和YZ，那么 WXYZ所在3×3区域与XZ、YZ所在列（行）的交集中的空格候选数不能为Z。

策略 15：四链数删减法，如果某个数字k在某4列（行）中只出现在相同的4行（列）中，则将从这四行（列）上其他的候选数中删除。

策略16：试探法，若某个空格的候选数只有两个时，进行试探填写其中一个候选数，若填写成功则该试探成功，若导致矛盾则另外一个候选数应填该空格。

以上介绍了常用的16数独策略，但是这些策略之间的难易程度如何划分呢，文中通过按照技术性和观察候选数的个数，初略的将这16个策略分为6个难度级别：

级别1：显性唯一候选数法、隐性唯一候选数法；

级别2：显性对数候选数法、隐性对数候选数法、交叉排除法；

级别3：显性三数集候选数法、隐性三数集候选数法、二链数删减法、XY形态匹配法；

级别4：显性四数集候选数法、隐性四数集候选数法、三链数删减法、XYZ形态匹配法；

级别5：四链数删减法、WXYZ形态匹配法；

级别6：试探法。

2 难度级别的划分方法

文中研究：给定一个数独谜题，如何定义以及确定它的难度？

笔者设计一个算法，让这个算法根据一套分级方法能将给定的数独谜题返回一个确定的“数值”代表它的抽象难度级别，定义数独谜题的难度级别通过人们解题的平均步数来划分。划分前的假设：为了衡量数独专家解决数独谜题的步数，必须模型化解数独谜题的步骤。对解题者有这样的假设：策略能按照难度分级，数独专家使用策略的原则是由易到难，文中使用的策略难度由第二部分已经给出。这样得出了数独难度级别的步数法，这种方法需要考虑完成一个数独谜题总共需要的步数，包括使用各个求解规则的步数。

划分问题的转化：当使用某个规则求解数独谜题时，满足条件的尝试会有很多次，但仅仅只有某些尝试才会成功，而通常多数情况下的尝试都会失败。每次尝试都会耗费时间，因此每次尝试都应该考虑时间。把每次尝试（不管其是否成功）都记作一步进行累加，最后统计完成题目时总共经历的步数。一个数独题目的难易程度就根据完成时所使用的总步数来确定。

人在使用某种策略求解数独谜题时，其选择符合条件的尝试是随机的，其是否成功也具有随机性。这样不同人使用该策略经过的步数会不同，那么以什么作为参考呢？通常最好的办法是使用不同人的平均值，在数学上就采用数学期望作为度量依据。

该问题可描述为：当面对某一数独题目，某策略可尝试的总情形为s种，其中可成功求解的情形有r种。假定每种情形都等可能出现，求平均经历多少次可首次成功。

因此，始终有：

这样，当通过计算机搜索得使用某种层次策略的总次数r，可成功的次数s，就可以通过（6）式计算得到首次成功平均经历的次数。

接下来考虑另一种情形：面对一个数独题目，采用某种层次策略，尝试了所有s种情形都没有成功，则记总步数T=s。

因此采用某个层次策略求解经历的总步数采用下式计算：

对任何一个级别的策略，计算使用该级别策略的总步数都采用（7）式计算。

设求解一个数独总共使用了L个级别的策略，则求解该数独的总步数为：

难度级别的划分，可根据求解总步数（8）来确定。

难度级别的划分，可根据求解总步数来确定。在文中将难度级别划分为4个级别，则需要选定3个临界值k1＜k2＜k3。当步数 d＜k1时，确定为第 1级；当步数时 k1≤d＜k2，确定为第 2级；当步数 k2≤d＜k3时，确定为第 3级；当步数 d≥k3时，确定为第4级。当然划分为其它难度级别也很容易变通，只要选定的不同的临界值即可。

现在可以模仿人工智能策略求解数独且生成难度了，具体步骤如下：

1）设定初始步数值d=0；

2）重复以下步骤直到数独谜题解出或者数独谜题无解：

①选择当前未使用过的最简单的策略级别求解数独，找出当前级别成功的次数r，若r＞0，则继续使用该级别的策略并使用公式（6）计算首次成功的期望值；若r=0，则跳到步骤②，并计算总经历的次数；

②使用比已经使用过的策略级别高一级别的策略级别，找出此级别成功的次数r，若r＞0，则继续使用该级别的策略并使用公式（6）计算首次成功的期望值；若r=0，则跳到步骤c，并计算总经历的次数；

③难度从低到高依次重新使用比b步骤策略级别难度低的策略级别，若其中有任何一个策略级别中，则跳回步骤a，否则使用比步骤b难度更高的策略级别。

3）根据上面的公式计算出总步数d，根据步数的区间输出难度值。

3 临界值的选定及合理性验证

尝试文献[7]中的4种难度（简单，适中，困难，极难）的数独谜题各100道，使用文中的人工智能求解算法求解他们，分别记录下求解这4种不同难度的数独谜题的步数，取平均值，得出以下4个数据：求解简单难度的数独谜题平均步数为10.64步、适中难度的步数为146.73步、困难难度的步数为317.12步、极难难度的步数为411.26步。

现在可以选定3个临界值k1、k2、k3，取这4个数字中两两相邻的平均值，即 k1=78.69、k2=231.93、k3=364.19，将数独谜题的难度等级分成4个：

1） d∈[1， 78.69）时，数独谜题难度为简单；

2） d∈[93.69， 231.93）时，数独谜题难度为适中；

3） d∈[281.93， 364.19）时，数独谜题难度为困难；

4）d＞364.19时，数独谜题难度为极难。

再次从文献[7]中的4种难度（简单，适中，困难，极难）中随机抽取100道数独谜题并对这400道数独谜题使用人工智能的步数法，求出解出这些谜题的步数所在的区间，将4个难度等级分级方法重新分级。结果如表1所示。

表1 重新划分难度级别的结果Tab.1 Result based on proposed difficulty metric mothod

进一步计算得到Goodman-Kruskal相关系数

由于r已经很大，因此我们有理由认为我们的数独谜题难度等级划分原则与文献[7]中数独谜题数独谜题难度等级划分原则具有较强的相关性，证实了难度划分原则的合理性。

4 结 论

模型化了求解数独谜题的过程，将求解数独谜题的过程拆分为16种策略6个级别由易到难的使用，根据使用策略的总步数将数独谜题的难度分为成了简单、适中、困难、极难这4个级别，并且通过文献[7]中400道数独谜题的数据分析，算出了Goodman-Kruskal相关系数为0.79，从而说明了我们的数独谜题难度级别的划分原则与文献[6]中的划分难度级别的原则具有很强的相关性，证明了这种分级方法的合理与有效。

当然，这种分级方式也并不是没有缺点，首先是策略的难易顺序问题，本文按照技术性和观察候选数的个数，这两个原则来评判策略的难易程度，实际上，还有很多其他的难易程度标准，当策略的顺序使用出现不一致时，步数的差别会很大，这样相应的临界值选择又将发生变化，至于如何分配策略的顺序使数独谜题难度的分级更加合理，是下一步研究的问题。另外本文只将数独谜题难度分成了4个，当然可以分的更细，让差异度更加明显。

[1]雷蕾，沈福可.关于数独问题的算法的设计与实现 [J].电脑知识与技术，2007（2）：481-482.

LEI Lei，SHEN Fu-ke.The design and implementation of the algorithm aboutSudoku [J].ComputerKnowledgeand Technology，2007（2）：481-482.

[2]Gustavo S G，Palomino M.Solving Sudoku puzzles with rewriting rules[J].Electronic Notes in Theoretical Computer Science，2007（176）:79-93.

[3]肖华勇，田铮，马雷.数独基于规则的逐步枚举算法设计[J].计算机工程与设计，2010，31（5）:1035-1037.

XIAO Hua-yong，TIAN Zheng，MA Lei.The design of the stepwise enumerative algorithm based on rule about Sudoku[J].Computer Engineering&Design，2010，31（5）:1035-1037.

[4]Moraglio A，Togelius J.Geometric particle swarm optimization for the Sudoku puzzle[J].GECCO，2007（5）:118-125.

[5]SUN Bao-chen，SUN Xi-wei， Yue，et al.A new algorithm for generating unique-solution Sudoku[C]//Fourth International Conference on Natural Computation，2008.

[6]Stuart A.Show Candidates[EB/OL]. （2012-01-03）[2012-02-18]http://www.sudokuwiki.org/sudoku.htm.

[7]Moritz L.Sudoku Garden[EB/OL]. （2012-02-16），[2012-02-18]http://sudokugarden.de/en.