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

程 曦，肖华勇

（西北工业大学 理学院，陕西 西安 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区域那么我们称这两个单元格在同一个群组。……