人工智能项目建议书.docx

项目建议书
项目名称:数独游戏出题与求解设计
组 员： 李鹏程、吴渊
9:38九日
目录
一．项目说明 2
1.1 整体描述 2
1.2出题设计 2
1.3求解设计 2
二．解决方案 2
2.1 项目分析 2
2.2求解方案 3
2.3 出题方案 3
2.4求解方案 4
2.5 开发平台 4
2.6 数据结构 4
2.6.1 主要数组 4
2.6.2 主要函数 5
2.7 求解算法设计 6
2.7.1 有限递推 6
2.7.2 回溯 6
2.8 出题算法设计 7
2.8.1 生成终盘 7
2.8.2 挖洞算法 7
三．方案检测 8
四．项目安排 9
参 考 文 献 9

一．项目说明
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 主要数组
本项目中所用到的主要数组有：
①int sudoku[82］
该数组的用途是存储题目以及保存最终结果,所有的9×9个数字被依次存储在该数组中，空白处则初始化为0。之所以把数组范围设计成82 而不是81，是为了程序的易读性，使得数组元素的最大下标可达81,下同.
②int fix［82］
该数组的用途是若sudoku数组中某位置的数字不为空，则fix数组相应位置的元素值为1，否则为0，即fix数组是用来记录哪些位置的数字是已经确定下来的。
③int possible[82][10］
该数组的用途是记录所有未确定数字的所有可能性,possible数组各元素的值在初始化时被初始化为与其第二维的下标一致，即0-9（其中0表示空值）；在中间计算过程中，若发现第一维某位置的某种可能性已不复存在，则将第一维下标是该位置而第二维下标是该不再可能的数字的元素值改为-1。
④int review［82]
该数组的用途类似于栈,在回溯算法过程中起到至关重要的作用.回溯之前，要把所有fix数组中值为0的位置依次存放进review数组；回溯中，由低到高依次逐渐确定这些位置的数值，无法确定者(即1—9的数字都不适合者)则应当回退到前一个位置，并修改其fix数组中的值,依次类推,直至review数组所存放的所有位置的值都能确定（即题目完成)，或回退到最初点的前一个位置（即题目有误）。
2.6。2 主要函数
本项目中为实现算法的数据结构所用到的主要函数如下：
①void setPossible（）
该函数是用来设置possible数组中元素的值，其具体功能是:对于fix数组中每一个值为0的位置（即对于每一个没有确定下数字的位置），考察其可能的数字是哪些,并记录下来。考察的方法是：在1-9这些数字中除去在当前行、列、九宫中已有的数字,剩下的即为可能的取值对象。
②bool fixPossible（）
该函数是用来修改fix数组和possible数组中元素的值，其返回值表示了在此次运行该函数过程中是否执行了修改。其具体功能是:对于fix数组中每一个值为0的位置(即对于每一个没有确定下数字的位置），考察其可能的数字的个数, 若为1,则将fix数组该位置的值改为1且sudoku数组该位置的值改为该唯一可能的数字(即该位置的值已确定下来）,且返回真；若没有只有一种可能性的位置, 则返回假。
③bool isExist（int i，int j)
该函数用于回溯过程中，其用途是：判断sudoku数组中位置为i的元素的值是否可能为j,即判断的是位置i所在的行、列以及九宫中是否已经存在数字j，若存在则返回真，否则返回假。
2.7 求解算法设计
前人的经验证明，回溯法是解决数独问题的有效方法，有着较快的解题速度.然而一般的常用的回溯算法仍然有不足之处，比如会进行重复的运算.所以在采用回溯法之前，还可以利用一点小小的技巧，以缩短回溯算法的运行时间，甚至可将运行时间缩短接近于0。这个小技巧即在回溯算法的基础上，再采用有限递推算法进行预处理，算法的基本框架是：
2.7。1 有限递推
在执行一次fixPossible函数之后，就可能会确定下一些原来没有确定的数字，那么此时possible数组的值必然也会变动。这是因为确定下的数字越多，某些位置的可能数字的数目就会减少，那么此时就应再执行setPossible函数修改possible数组。而修改之后可能又会出现一些只有一种可能性的位置，那么就应该再执行fixPossible函数。于是,只要如此循环往复下去，就能最大限度地确定下根据题目本身含义和规则而确定下的内容。确定的数字越多，对于将来回溯也就越有利。经验表明，有些数独题直接就可以通过执行大约10多次的有限递推循环体解决。一般情况下，有限递推的循环结束只有两种情况：一是推出了全部结果；二是fixPossible函数返回值为假，即不存在只有一种可能性的位置。
2.7.2 回溯
回溯是数独求解算法中最为关键的部分，其主要步骤是：
①按下标的由低到高扫描fix数组，将值为0的位置记录进review数组，记录的顺序也是由低到高,最后记录下fix数组中为0位置的个数再加1；
②把review数组看作栈，记录栈顶；
③先设置一个bool型标志变量flag并初始化为true,下面各步骤都将在一个条件始终为真的死循环中进行，该循环由一条对flag进行真假判断的语句分成两大部分。若当前栈顶是经过了回退操作而达到的，则flag会已被记录为false;否则flag为true。死循环结束的条件是review数组（栈）中top与max的值相等，即解出最终结果，或者是无解，最终top小于0。在死循环中，若flag为true,则进入步骤④,否则进入步骤⑤。
④若flag为true,则说明栈顶是经过正常的假设而达到的，并非由回退达到, 那么根据possible数组以及isExist函数对栈顶所保存位置的可能出现的数字进行判断,把遇到的第一个可能数字放进sudoku数组，并把fix数组的该位置的值设为1，并判断是否已经解出结果，即review数组（栈）中top和max的值是否相等.若相等，则得出结果并退出死循环；若发现1—9都不可能应用在栈顶所保存的位置，则说明前面的假设有错误，此时应当回退.即fix数组和sudoku数组的该位置重设为0，top减1，并将flag的值设为false.然后结束本轮循环体,继续下一轮的循环。
⑤若flag为false，说明是经过了回退才达到现在这个栈顶的，那么若仍然没有可能的数字可以应用在当前栈顶所保存的位置上，则继续执行出栈操作，即fix数组和sudoku数组的该位置的值重设为0，top减1；否则将遇到的第一个可能数字应用到该位置，即再设好sudoku数组和fix数组,将top加1，并将flag的值设为true。然后结束本轮循环体,继续下一轮的循环。
2。8 出题算法设计
整个生成数独题的算法分为两步执行:先利用拉斯维加斯随机算法随机生成一个填满数字且符合游戏规则的终盘；而后根据所需求的难度等级抹去一些数字,每抹去一个数字就验证一次解的唯一性。如此往复直至满足所需的难度要求为止,最后通过适当的等价对称变换后输出该题，算法的基本框架是：
2.8.1 生成终盘
数独出题时要先采用拉斯维加斯算法随机生成一个数独题的终盘.首先,在一个数独空盘中随机选中n个格子，在这些格子内随机填人数字1-9；然后，调用数独求解算法对这个已知n格的数独题S（n）进行求解。如果S(n）有解，则返回true，否则返回false。拉斯维加斯算法的思想便是不断重复执行上述步骤，直至其返回值为true为止.
2.8。2 挖洞算法
挖洞算法的基本思想就是挖去一个数独终盘上的一些格子,使其成为有唯一解的数独题目。然而挖洞的机制是多种多样的，本项目为了加快出题算法的速度，将贪心算法机制引入到挖洞算法当中.整个挖洞算法流程中的5个关键步骤如下：
①确定挖洞顺序
确定挖洞顺序即在一个终盘上，决定哪个位置的格子先被挖去,哪个格子是下一个，该顺序对生成的题目中已知格的分布起决定性作用。本项目中选择了3中有着不同难度效果挖洞顺序，由易到难依次是：全盘随机、间隔、蛇形。
②挖洞约束
根据难度等级的定义，本项目对挖洞操作加入两个约束来影响已知格的分布形势:第一，已知格数最多为81格,将1—81大致均分为3个区间，对应到3个难度等级，已知格越少则题越难.若游戏者需要某个难度的数独题，则在其对应的区间内随机一个数作为已知格数的下界，即当挖洞至剩余格数达到下界时停止；第二,同理，每行、每列剩余的格数必须多于难度等级所规定的下界，否则禁止此次挖洞操作。每尝试挖去一个格子，都要检验一次挖去该格后是否与这两个约束冲突,一旦冲突则禁止此次挖洞。
③反证法判断解的唯一性
借助反证法的思想来随时检验当一个格子中的数字被挖去后，是否能保证此题还有唯一的解。
④剪枝优化
通过剪枝优化来降低耗费在挖洞尝试中的时间。
⑤等价变换
为了增加所出题目的多样性，对完成以上操作后得到的数独题目进行等价变换,得到新的数独题目。
三．方案检测
①对A、B、C三个不同难度的已知数独问题(难度A〈B〈C）进行多次运行测试，进行定性分析,验证计算结果的正确性,记录并对比运算速度。
②多次运行程序提出数独问题,验证提出的数独问题的合理性,记录并对比运算速度.
四．项目安排
任务
负责人
时间
项目建议书
李鹏程、吴渊
9.3-9。9
数独求解功能
李鹏程、吴渊
10。1-10.21
数独出题功能
李鹏程、吴渊
10.1-10.21
测试
李鹏程、吴渊
10。22-10。23
中期进展报告
李鹏程、吴渊
10。24-10.28
界面
李鹏程、吴渊
10。29-11.4
功能集成
李鹏程、吴渊
11.5—11。9
测试与改进
李鹏程、吴渊
11.10—11。20
完成总结报告
李鹏程、吴渊
11。21—11.25
参 考 文 献
［1］ 刘晓宝.数独游戏的解题算法[J].电脑编程技巧与维护,2007，(5）:64- 67。
［2] 严蔚敏,吴伟民。数据结构[M］.第二版.北京:清华大学出版社，1993:93- 95,43— 45,220— 221。
［3] Stanley B Lippman, Josee Lajoie 著，潘爱民等译。 C++ Primer( 第三版） ［M］. 中 国电力出版社，2002.
[4] 王晓东.算法设计与分析［M].第一版.清华大学出版社，2003。
［5］ 王万良.人工智能及其应用[M].第二版.高等教育出版社,2008。