项目建议书
项目名称：数独游戏出题与求解设计 组员：李鹏程、吴渊
二〇一五年十一月九日
目录
一．项目说明 ........................................................................................................................... 3 1.1 整体描述 ........................................................................................................................... 3 1.2出题设计 ............................................................................................................................ 3 1.3求解设计 ............................................................................................................................ 3 二．解决方案 ........................................................................................................................... 3 2.1 项目分析 ........................................................................................................................... 3 2.2求解方案 ............................................................................................................................ 4 2.3 出题方案 ........................................................................................................................... 4 2.4求解方案 ............................................................................................................................ 5 2.5 开发平台 ........................................................................................................................... 5 2.6 数据结构 ........................................................................................................................... 5
2.6.1 主要数组 ............................................................................................................... 5 2.6.2 主要函数 ............................................................................................................... 6 2.7求解算法设计 .................................................................................................................... 7
2.7.1 有限递推 ............................................................................................................... 7 2.7.2 回溯 ....................................................................................................................... 7 2.8出题算法设计 .................................................................................................................... 8
2.8.1 生成终盘 ............................................................................................................... 8 2.8.2 挖洞算法 ............................................................................................................... 8
三．方案检测 ................................................................................................................................... 9 四．项目安排 ................................................................................................................................. 10 参考文献......................................................................................................................................... 10
一．项目说明 1.1 整体描述
数独游戏是一种数学方面的游戏，直观上更像一种拼图游戏，其游戏规则是：在9×9的大九宫格内，已给定若干数字，其他宫位留白，玩家需自己按照逻辑推敲出剩下的空格里是什么数字；必须满足的条件：每一行与每一列都有1到9的数字，每个小九宫格里也有1到9的数字，并且一个数字在每行、每列及每个小九宫格里只能出现一次，既不能重复也不能少；每个数独游戏都可根据给定的数字为线索，推算解答出来。
1.2出题设计
本项目计划设计一种算法，在短时间内生成数独题且难度等级不一致，以满足不同水平游戏者的需求。数独游戏挑战者的水平各异，对数独题目的难度要求各不相同，但是有三个方面需要注意：可变化的难度、解的唯一性和算法复杂度最小化。
1.3求解设计
本项目的目的就是按照数独游戏的规则，综合运用数据结构的分析和人工智能的算法，利用计算机程序来实现对已知数独游戏的快速求解。
二．解决方案 2.1 项目分析
数独虽然号称是数学问题, 但在求解时几乎用不上数学运算方法，事实上它更像是一种思维方式。数独游戏开始后，要想在空格中填入正确的数字，先要根据数独游戏规则对1-9分别进行逻辑判断，然后选择正确的数字填入空格。另外，
由于某个格子填入数据时，有可能还要对原来已填入的数据进行修正，所以可以考虑使用递推和回溯搜索来求解数独问题。
出题时，要能保证算法生成的数独题具有可变化的难度和唯一解,该算法内部应该包含有对数独题的求解和评级功能。本项目使用了一种基于“挖洞”思想的数独题生成算法，将该算法的设计工作分为评级、求解和生成三部分工作。首先，根据游戏者需要的难度等级，我们从已知格的总数和分布以及穷举求解的搜索次数这三个方面特性，通过赋权求和来评估一个数独题的难度等级。然后，运用反证法思想，并结合深度优先搜索求解器一起论证一个“洞”被“挖去”后是否能保证该题有唯一解。最后，通过避免重填一个被“挖去”的格子，或者回溯到一个曾经无法“挖去”的格子，来降低算法的复杂性。
2.2求解方案
解决该数独求解问题时的要考虑的主要方面有： ①从界面或文本读取数独游戏数据；
②判断题目合法性，即验证给出数据本身是否符合游戏规则，行、列以及小九宫中从不重复地出现数字1-9； ③逐个取得空白处；
④采用递推算法，若可以填入数字则填入数字，并入栈以便回溯，否则回溯至前面填入数字处重新填数； ⑤所有空白处都要填满数据； ⑥输出结果至屏幕或文件。
如此看来，最需要仔细考虑的就是如何通过递推算法填入正确的数字，或者通过回溯算法重新填入数字并得到最终解，这个也就是本项目算法的核心，同时也是解题的关键。
2.3 出题方案
要想设计一个算法用以生成各种难度等级的数独题，通过对游戏规则的分析，首先从以下三个方面定义难度等级：已知格总数、已知格的分布和穷举搜索复杂度。
本算法采用“挖洞”思想，经过以下两步生成数独题： ①运用拉斯维加斯随机算法生成一个终盘； ②根据所需要的难度等级选取一种挖洞顺序；
③制定两个约束来控制已知格的分布；
④通过深度优先搜索来求解，从而保证“挖去”一个数字后该数独题仍有唯一解；
⑤引入剪枝技术来避免无效的“挖洞”尝试；
⑥对“挖好洞”的数独题进行等效对称变换，以提高游戏题目的多样性。
2.4求解方案
①利用递推和回溯法完成数独问题求解功能；
②利用拉斯维加斯随机算法、深度优先搜索和剪枝技术完成数度问题出题功能；
③完成界面良好的数独游戏程序。
2.5 开发平台
本项目基于Visual Studio 2010平台的MFC，采用C++语言进行开发与测试。
2.6 数据结构
通常情况下，精心选择的数据结构可以带来拥有更高的运行或存储效率的算法。一般认为，一个数据结构是由数据元素依据某种逻辑联系组织起来的，对数据元素间逻辑关系的描述称为数据的逻辑结构；数据必须在计算机内存储, 数据的存储结构是数据结构的实现形式， 是其在计算机内的表示。数独从形式上看是一个方阵, 十分适合用数组来表示。
2.6.1 主要数组
本项目中所用到的主要数组有： ①intsudoku[82]
该数组的用途是存储题目以及保存最终结果,所有的9×9个数字被依次存储在该数组中，空白处则初始化为0。之所以把数组范围设计成82 而不是81，是为了程序的易读性，使得数组元素的最大下标可达81，下同。
②int fix[82]