数独游戏课程设计报告

第第页数独游戏课程设计报告

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

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

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

1终盘和初盘生成

首先运用初等行、列变换，构造一个新的简约明白的终盘生成算法，详细步骤如下：

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

Step2：从列的角度出发，仍旧以小九宫为单位，把第一个小九宫的第一列的相邻三个数字为一个集体进行交替，由此获得第四个小九宫的一列数字，第一小九宫的第二、三列也通过这个相同的方法而得到第四个小九宫的其他两列数字。剩余的其他小九宫也依据前述相同的方法可以得到，

将已得到的一个终盘，恰当隐去某些格子内的值，使之成为合乎数独规章的空格，由此便生成一个数独谜题，即初盘。此处，我们隐去的.格子的方法是通过概率随机隐去相应的格子数，由于我们所创建的终盘是保证唯一性的，所以此处径直借助终盘来进行检验初盘的唯一性。

2难度划分

在上面的步骤中，我们完成了由终盘生成初盘的过程。在得到巨大的初盘后，由于每个初盘的空格数、空格位置不同，导致了它们的难度不同。因此，我们首先需要依据这些初盘，建立一个评分模型，得到每个初盘的难度评分值，再依据这些评分值划分不同等级的数独。

2.1评分模型建立

我们基于仿照人工求解的方式充分运用基本方法，直到基本方法不再起作用时才运用高级方法。因此基于常用的两个算法―显性唯一候选数法和隐含唯一候选数法，以及高级方法，我们假设每个玩家对于每一个空格的求解按以下步骤进行：

Step1：当玩家第一次运用显性唯一候选数法能解出数独谜题的一个空格，那么转向下一个空格的求解；

Step2：当玩家第一次运用显性唯一候选数法不能求解时，那么采纳隐性唯一候选法，假设能求解出该空格，那么进行下一个空格的求解；

Step3：当玩家先后采纳显性唯一候选数和隐含唯一候选数法，依旧不能找出答案，这时利用计算机随机自动生成一个空格的答案，称此方法为高级方法，然后玩家便可以继续进行下一个空格的求解；

Step4：当求出一个数独谜题的全部空格值，游戏结束。

假设N1为基本方法中运用显性唯一数法的次数，N2为基本方法中运用隐性唯一数法的次数，N3为运用高级方法的次数，α，β，γ分别为不同方法的权重，从而我们建立一个难度评分模型：

Score=αN1+βN2+γN3

由于高级方法比基本方法的难度大，并且对于同一方法，运用2次要比1次的难度大。所以，为了表达“数独”题目运用不同方法及其相应次数的繁复度，我们给不同的方法加上适当的权重。本文定义的权重如下：α=1，β=2，γ=5

对于上述权重，根据随着方法难度系数递增权重递增的方式以及尽可能运用不同方法间的权重差异足够大的原那么进行取值。虽然权重的取值有肯定的任意性，但通过计算机仿真可以说明这样能很好的区分不同难度等级的“数独”题目。

2.2计算机仿真

依据我们建立的终盘，随机产生1200道题目，然后用本文的人工智能算法求解，并记录不同题目各种方法运用次数、空格数以及最终分数。此处，选取部分仿真结果如表1所示：

由表1所知：评分数涵盖区域较大，有些高难度的初盘的score很大，偏离了初盘score的平均值，不便于我们依据全部初盘的score径直划分难度级别，故我们进行归一化，将每个初盘的score归一到[0，1]范围内，建立公式如下：

其中：a