数独游戏的难度划分及创建算法设计

龙源期刊网 https://www.wendangku.net/doc/4a17353700.html,

数独游戏的难度划分及创建算法设计

作者：王新鑫李星钟宁

来源：《计算机光盘软件与应用》2013年第18期

摘要：将“数独”智力游戏的难度划分与创建问题分解为建立终盘和初盘、难度评分、游戏创建。首先采用行列变换的方法建立终盘，然后隐去部分数字并检验解唯一性，得到初盘。在已得到初盘的基础上，根据求解时初级方法和高级方法使用的次数确定难度评分，从而依据分数对题目的难度进行划分，以此创建不同等级难度的“数独”游戏。最后通过实验验证了模型的实用性。

关键词：数独；难度划分；评分模型；计算机仿真

中图分类号：TP18；O156

“数独”是18世纪瑞士数学家欧拉发明。该游戏是在9×9的单元网格中进行，这些网格被分9行、9列和3×3个九宫格。单元网格中已有若干数字，其余均为空格。玩家需要推理出所有剩余空格的数字，并满足每一行、每一列、每一个小九宫格内的数字均含1-9且不重复。每一道合格的“数独”谜题都有且仅有唯一答案。

目前，“数独”作为一种智力游戏已经风靡世界，国内外许多学者已对数独的求解算法做了深入研究，例如递归法[1]、回溯候选数法[2]、枚举算法[3]等，但在数独的难度划分与创建方面的研究还很少。由于影响“数独”难度的因素有很多，就问题本身而言，难度因素包括最高难度的技巧、各种技巧所用次数、是否有隐藏及隐藏的深度和广度的技巧组合、当前盘面可逻辑推导出的个数等等；就玩家而言，了解的技巧数量、熟练程度、观察力等也属于难度划分应考虑的因素。因此，单单利用空格数或求解时间对题目难度进行划分是不全面的，其难度指标定义过于主观，讨论也不够细致，无法真正划分难度的级别。

本文首先创建符合要求的“数独”终盘，然后在终盘的基础上生成具有数独特性的初盘，根据求解时初级方法和高级方法使用的次数确定难度评分，从而依据分数对题目的难度进行划分，以此创建不同等级难度的“数独”游戏。

1 终盘和初盘生成

首先运用初等行、列变换，构造一个新的简单明了的终盘生成算法，具体步骤如下：

Step1：从行的角度出发，在第一行随机输入1-9的数字。以一个小九宫为单位，将相邻三个数字作为一个集体进行交替，由此获得第二行的数字，再由第二行的数字根据前述方法变换得到第三行的数字。由此我们得到一个前三行，共有三个小九宫的全部数字。变换过程如图1（a）（b）所示：