数独游戏课程设计报告

1、数独游戏课程设计报告将“数独”智力游戏的难度划分与创建问题分解为建立终盘和初盘、难度评分、游戏创建。首先采用行列变换的方法建立终盘，然后隐去部分数字并检验解唯一性，得到初盘。在已得到初盘的基础上，根据求解时初级方法和高级方法使用的次数确定难度评分，从而依据分数对题目的难度进行划分，以此创建不同等级难度的“数独”游戏。最后通过实验验证了模型的实用性。下面是的数独游戏课程设计报告，欢迎来参考！“数独”是18世纪瑞士数学家欧拉发明。该游戏是在9X9的单元网格中进行，这些网格被分9行、9列和3X3个九宫格。单元网格中已有若干数字，其余均为空格。玩家需要推理出所有剩余空格的数字，并满足每一行、每一列、每

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

3、，无法真正划分难度的级别。本文首先创建符合要求的“数独”终盘，然后在终盘的基础上生成具有数独特性的初盘，根据求解时初级方法和高级方法使用的次数确定难度评分，从而依据分数对题目的难度进行划分，以此创建不同等级难度的“数独”游戏。1 终盘和初盘生成首先运用初等行、列变换，构造一个新的简单明了的终盘生成算法，具体步骤如下：Step1：从行的角度出发，在第一行随机输入1-9的数字。以一个小九宫为单位，将相邻三个数字作为一个集体进行交替，由此获得第二行的数字，再由第二行的数字根据前述方法变换得到第三行的数字。由此我们得到一个前三行，共有三个小九宫的全部数字。Step2：从列的角度出发，仍然以小九宫为单位

4、，把第一个小九宫的第一列的相邻三个数字为一个集体进行交替，由此获得第四个小九宫的一列数字，第一小九宫的第二、三列也通过这个相同的方法而得到第四个小九宫的其他两列数字。剩余的其他小九宫也根据前述相同的方法可以得到，将已得到的一个终盘，恰当隐去某些格子内的值，使之成为合乎数独规则的空格，由此便生成一个数独谜题，即初盘。此处，我们隐去的格子的方法是通过概率随机隐去相应的格子数，由于我们所创建的终盘是保证唯一性的，所以此处直接借助终盘来进行检验初盘的唯一性。2 难度划分在上面的步骤中，我们完成了由终盘生成初盘的过程。在得到庞大的初盘后，由于每个初盘的空格数、空格位置不同，导致了它们的难度不同。因此，我

5、们首先需要依据这些初盘，建立一个评分模型，得到每个初盘的难度评分值，再根据这些评分值划分不同等级的数独。2.1 评分模型建立我们基于模仿人工求解的方式充分使用基本方法，直到基本方法不再起作用时才使用高级方法。因此基于常用的两个算法显性唯一候选数法和隐含唯一候选数法，以及高级方法，我们假设每个玩家对于每一个空格的求解按以下步骤进行：Step1：当玩家第一次使用显性唯一候选数法能解出数独谜题的一个空格，则转向下一个空格的求解；Step2：当玩家第一次使用显性唯一候选数法不能求解时，则采用隐性唯一候选法，若能求解出该空格，则进行下一个空格的求解；Step3：当玩家先后采用显性唯一候选数和隐含唯一候选

6、数法，依然不能找出答案，这时利用计算机随机自动生成一个空格的答案，称此方法为高级方法，然后玩家便可以继续进行下一个空格的求解；Step4：当求出一个数独谜题的所有空格值，游戏结束。假设N1为基本方法中使用显性唯一数法的次数，N2为基本方法中使用隐性唯一数法的次数，N3为使用高级方法的次数，%,(3,丫分别为不同方法的权重，从而我们建立一个难度评分模型：Score=%N1+BN2+yN3由于高级方法比基本方法的难度大，并且对于同一方法，使用2次要比1次的难度大。所以，为了体现“数独”题目使用不同方法及其相应次数的复杂度，我们给不同的方法加上适当的权重。本文定义的权重如下：=1,(3=2,丫=5对于上述权重，按照随着方法难度系数递增权重递增的方式以及尽可能使用不同方法间的权重差异足够大的原则进行取值。虽然权重的取值有一定的随意性，但通过计算机仿真可以表明这样能很好的区分不同难度等级的“数独”题目。2.2计算机仿真依据我们建立的终盘，随机产生1200道题目，然后用本文的人工智能算法求解，并记录不同题目各种方法使用次数、空格数以及最终分数。此处，选取部分仿真结果如表1所示：由表1所知：评分数涵盖区域较大，有些高难度的初盘的score很大，偏离了初盘score的平均值，不便于我们依据所有初盘的score直接划分难度级别，故我们进行归一化，将每个初盘的score归一到0，1范围内，建立公式如