人工智能项目建议书

项目建议书项目建议书 项目名称 数独游戏出题与求解设计 组 员 李鹏程 吴渊 二 二 二 二 年三月九日 目录目录 一 项目说明 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