人工智能完成总结报告

精品文档 1欢迎下载 完成总结报告完成总结报告 项目名称 数独游戏设计与实现 组 员 王郑合 2014204081 栾杰 2014204080 文宽 2014204104 二 二 二 二 年四月二十四日 精品文档 2欢迎下载 1 问题描述 1 1 问题说明 数独游戏起源于瑞士 由十八世纪的瑞士数学家欧拉发明 是一种数字拼 图游戏 其游戏规则是 在 9 9 的大九宫格内 已给定若干数字 其他宫位留白 玩家需自己按 照逻辑推敲出剩下的空格里是什么数字 必须满足的条件 每一行与每一列都有 1 到 9 的数字 每个小九宫格里 也有 1 到 9 的数字 并且一个数字在每行 每列及每个小九宫格里只能出现一 次 既不能重复也不能少 每个数独游戏都可根据给定的数字为线索 推算解答出来 1 2 数独求解描述 由于数独游戏的推广与普及 在当今世界上有着大量的数独爱好者 本项 目的目的就是按照数独的游戏规则 通过对数据结构的分析和人工智能算法的 研究 利用计算机程序来实现对已知数独游戏的快速求解 1 3 数独出题描述 数独游戏挑战者的水平各异 对数独题目的难度要求各不相同 所以本项 目致力于设计一种算法 使其在尽可能短的时间内生成不同难度等级的数独题 以满足不同水平游戏者的需求 同时 该算法还要考虑到三个方面要求 可变 化的难度 解的唯一性和算法复杂度最小化 精品文档 3欢迎下载 2 功能分析 2 1 数独求解 数独虽然号称是数学问题 但在求解时几乎用不上数学运算方法 事实上 它更像是一种思维方式 数独游戏开始后 要想在空格中填入正确的数字 先 要根据数独游戏规则对1 9分别进行逻辑判断 然后选择正确的数字填入空格 另外 由于某个格子填入数据时 有可能还要对原来已填入的数据进行修正 所以可以考虑使用递推和回溯搜索来求解数独问题 2 2 数独出题 出题时 要能保证算法生成的数独题具有可变化的难度和唯一解 该算法内 部应该包含有对数独题的求解和评级功能 本项目使用了一种基于 挖洞 思 想的数独题生成算法 将该算法的设计工作分为评级 求解和生成三部分工作 利用随机数出现的概率不同来确定不同的难度 通过避免重填一个被 挖去 的格子 或者回溯到一个曾经无法 挖去 的格子 来降低算法的复杂性 2 3 题目保存 当用户需要退出却仍没有完成数独题目的解答时 可以选择是否保存当前 的求解进度 如果需要 本系统会帮助用户将目前未完成的数独题目的解答进 度保存起来 以便用户下次使用本系统时 可以继续解答上次未完成的题目 2 4 题目读取 用户可以在程序开始运行后 选则读取一道之前保存起来的题目进行解答 被读取的题目将会显示到程序界面上 精品文档 4欢迎下载 3 系统设计 3 1 功能结构图 本程序主要有数独求解和数独出题两个功能 数独求解包括题目检验 解 题和输入输出 数独出题包括答案检验 难度选择 出题和输入输出 精品文档 5欢迎下载 3 2 业务流程图 3 3 类图 SudokuDlg 类 程序的界面类 精品文档 6欢迎下载 Solve 类 实现数独题目求解功能 Make 类 实现数独题目出题功能 Pre 类 对数据进行预处理 3 4 界面设计 3 5 算法设计 3 5 1 数独求解算法 解决该数独求解问题时的要考虑的主要方面有 判断题目合法性 即验证给出数据本身是否符合游戏规则 行 列以及 小九宫中从不重复地出现数字1 9 采用递推算法 若可以填入数字则填入数字 并入栈以便回溯 否则回 溯至前面填入数字处重新填数 所有空白处都要填满数据 其中 最重要的就是如何通过递推算法填入正确的数字 或者通过回溯算 法重新填入数字并得到最终解 这是本算法的核心内容 回溯法是解决数独问题的有效方法 有着较快的解题速度 然而一般的常 用的回溯算法仍然有不足之处 比如会进行重复的运算 所以在采用回溯法之 前 还可以利用一点小技巧 以缩短回溯算法的运行时间 甚至可将运行时间 缩短接近于0 这个小技巧即在回溯算法的基础上 采用有限递推算法进行预处 理 精品文档 7欢迎下载 算法活动图如下 3 5 1 数独出题算法 要想设计一个算法用以生成各种难度等级的数独题 通过对游戏规则的分 析 首先从三个方面定义难度等级 分别是已知格总数 已知格的分布和穷举 搜索复杂度 本算法采用 挖洞 思想 经过以下步骤生成数独题 用随机算法生成一个数独题目 用求解算法生成终盘 根据难度挖去部分数字 整个生成数独题的算法分为两步执行 先 利用拉斯维加斯随机算法随机生成一个填满数 字且符合游戏规则的终盘 而后根据所需求的 难度等级抹去一些数字 难度等级由随机数出 现的概率来决定 算法活动图如下 精品文档 8欢迎下载 4 系统实现 4 1 开发平台 本项目基于 Visual Studio 2010 平台的 MFC 采用 C 语言进行开发与测 试 4 2 运行环境 本项目可在各个版本的 Win7 系统或者 Windows XP 系统下运行 4 3 数据结构 数据结构是计算机存储 组织数据的方式 通常情况下 精心选择的数据 结构可以带来拥有更高的运行或存储效率的算法 一般认为 一个数据结构是 由数据元素依据某种逻辑联系组织起来的 对数据元素间逻辑关系的描述称为 精品文档 9欢迎下载 数据的逻辑结构 数据必须在计算机内存储 数据的存储结构是数据结构的实 现形式 是其在计算机内的表示 数独从形式上看是一个方阵 十分适合用数 组来表示 4 3 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数组所 存放的所有位置的值都能确定 即题目完成 或回退到最初点的前一个位置 即题目有误 4 3 2 相关函数 本项目中为实现算法的数据结构所用到的主要函数如下 void setPossible 该函数是用来设置 possible 数组中元素的值 其具体功能是 对于 fix 数 组中每一个值为 0 的位置 即对于每一个没有确定下数字的位置 考察其可能 的数字是哪些 并记录下来 考察的方法是 在 1 9 这些数字中除去在当前行 列 九宫中已有的数字 剩下的即为可能的取值对象 bool fixPossible 精品文档 10欢迎下载 该函数是用来修改fix数组和possible数组中元素的值 其返回值表示了在 此次运行该函数过程中是否执行了修改 其具体功能是 对于fix数组中每一个 值为0的位置 即对于每一个没有确定下数字的位置 考察其可能的数字的个 数 若为1 则将fix数组该位置的值改为1且sudoku数组该位置的值改为该唯 一可能的数字 即该位置的值已确定下来 且返回真 若没有只有一种可能性 的位置 则返回假 bool isExist int i int j 该函数用于回溯过程中 其用途是 判断sudoku数组中位置为i的元素的值 是否可能为j 即判断的是位置i所在的行 列以及九宫中是否已经存在数字j 若存在则返回真 否则返回假 4 4 求解算法实现 4 4 1 有限递推 在执行一次fixPossible函数之后 就可能会确定下一些原来没有确定的数 字 那么此时possible数组的值必然也会变动 这是因为确定下的数字越多 某些位置的可能数字的数目就会减少 那么此时就应再执行setPossible函数修 改possible数组 而修改之后可能又会出现一些只有一种可能性的位置 那么 就应该再执行fixPossible函数 于是 只要如此循环往复下去 就能最大限度 地确定下根据题目本身含义和规则而确定下的内容 确定的数字越多 对于将 来回溯也就越有利 经验表明 有些数独题直接就可以通过执行大约10多次的 有限递推循环体解决 一般情况下 有限递推的循环结束只有两种情况 一是 推出了全部结果 二是fixPossible函数返回值为假 即不存在只有一种可能性 的位置 预处理的主要代码见附录 4 4 2 回溯 回溯是数独求解算法中最为关键的部分 其主要步骤是 按下标的由低到高扫描fix数组 将值为0的位置记录进review数组 记 录的顺序也是由低到高 最后记录下fix数组中为0位置的个数再加1 把review数组看作栈 记录栈顶 先设置一个bool型标志变量flag并初始化为true 下面各步骤都将在一 个条件始终为真的死循环中进行 该循环由一条对flag进行真假判断的语句分 成两大部分 若当前栈顶是经过了回退操作而达到的 则flag会已被记录为 精品文档 11欢迎下载 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 然后结束本轮循环体 继续下一轮的循环 回溯的主要代码见附录 4 5 出题算法实现 4 5 1 生成终盘 数独出题时要先采用拉斯维加斯算法随机生成一个数独题的终盘 首先 在一个数独空盘中随机选中 n 个格子 在这些格子内随机填人数字 1 9 然后 调用数独求解算法对这个已知 n 格的数独题 S n 进行求解 如果 S n 有解 则 返回 true 否则返回 false 拉斯维加斯算法的思想便是不断重复执行上述步 骤 直至其返回值为 true 为止 生成随机数的主要代码见附录 4 5 2 挖洞算法 挖洞算法的基本思想就是挖去一个数独终盘上的一些格子 使其成为有唯 一解的数独题目 然而挖洞的机制是多种多样的 本项目为了加快出题算法的 速度 利用不同的随机挖洞概率来区分不同的难度 挖洞的主要代码见附录 精品文档 12欢迎下载 4 6 程序运行截图 开始 数独求解 手动输入题目 数独求解 读取保存的题目 解出答案 精品文档 13欢迎下载 数独出题 选择难度 得出题目 保存题目 保存和打开题目的文件格式 精品文档 14欢迎下载 5 测试 5 1 解题测试 选取 5 个难度共 25 道不同的数独题目进行解题测试 记录程序运行时间 检验运算结果是否正确 并对实验结果进行分析 难度 1 题目12345Average 时间14ms13ms22ms22ms20ms18 2ms 结果正确正确正确正确正确 难度 2 题目12345Average 时间21ms20ms20ms33ms21ms23 0ms 结果正确正确正确正确正确 精品文档 15欢迎下载 难度 3 题目12345Average 时间22ms26ms25ms23ms26ms24 4ms 结果正确正确正确正确正确 难度 4 题目12345Average 时间28ms24ms35ms29ms26ms28 4ms 结果正确正确正确正确正确 难度 5 题目12345Average 时间28ms50ms22ms44ms29ms34 6ms 结果正确正确正确正确正确 通过对实验数据的分析可知 本算法得出的结果全部正确 说明本算法成功实现了通过计算机人工智 能方法对数独问题求解 随着题目难度加大 平均运行时间逐渐加长 本次试验中 运行时间最长的题目不超过 50ms 大多数题目在 20 30ms 内完成 说明本算法的运行速度是比较快捷的 5 2 出题测试 5 个难度各进行 5 次数独出题运算 记录运行时间 并比较得出的题目是否 会有重复 难度 1 题目12345Average 时间9ms10ms6ms7ms9ms8 2ms 重复 无 难度 2 精品文档 16欢迎下载 题目12345Average 时间9ms8ms9ms7ms8ms8 2ms 重复 无 难度 3 题目12345Average 时间9ms9ms6ms5ms9ms7 6ms 重复 无 难度 4 题目12345Average 时间10ms9ms8ms6ms11ms8 8ms 重复 无 难度 5 题目12345Average 时间7ms9ms10ms5ms10ms8 2ms 重复 无 通过对实验数据的分析可知 本此实验中 各组均无重复的题目出现 说明本算法成功实现了通过计 算机人工智能方法对数独问题的出题 程序的运行时间不随难度增加而加长 个难度的运行时间基本一样 运行时间基本维持着 8 9ms 左右 说明本算法的运行速度是比较快捷的 6 工作总结 较好地完成了数独求解和数独出题的算法的设计与实现 对算法进行功能测试 验证了算法的有效性 并证明了算法具有良好的 精品文档 17欢迎下载 时间效率 实现了良好的用户界面 实现了数独题目的读取和保存功能 通过本项目 对人工智能技术有了进一步的了解 并初步掌握了 MFC 编 程 锻炼了团队合作能力 7 项目安排 任务负责人时间 项目建议书王郑合 文宽 栾杰 9 19 9 30 数独求解功能王郑合 栾杰 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 精品文档 18欢迎下载 参 考 文 献 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 附 录 预处理算法的主要代码 预处理算法的主要代码 while 1 setPossible if fixPossible sudoku fix possible 即不存在只有一种可能性的位置 break if isFull sudoku 若已推出全部结果 break if isFull sudoku printAll 输出结果 回溯算法的主要代码 回溯算法的主要代码 if isFull sudoku return true int top 0 精品文档 19欢迎下载 所有值为0的位置入栈 for int i 1 i 0 宏定义 用于调试程序 if flag int j for j 1 j max return 1 b