《《人工智能基础》实验报告-实验名称：数独游戏设计与实现》由会员分享，可在线阅读，更多相关《《人工智能基础》实验报告-实验名称：数独游戏设计与实现（20页珍藏版）》请在金锄头文库上搜索。
1、精品资料欢迎下载完成总结报告项目名称：数独玩耍设计与实现二一七年十二月二十四日1 问题描述1.1 问题说明数独玩耍起源于瑞士,由十八世纪的瑞士数学家欧拉制造,是一种数字拼图玩耍,其玩耍规章是：在 9 9 的大九宫格内,已给定如干数字,其他宫位留白,玩家需自己依据规律推敲出剩下的空格里是什么数字；必需中意的条件：每一行与每一列都有1 到 9 的数字,每个小九宫格里也有 1 到 9 的数字,并且一个数字在每行、每列及每个小九宫格里只能显现一次, 既不能重复也不能少；每个数独玩耍都可依据给定的数字为线索,推算解答出来；EFIEFNEUGBFNKFMEINGFEJFBNEIFKDNF精品资料欢迎下载1
2、.2 数独求解描述由于数独玩耍的推广与普及, 在当今世界上有着大量的数独爱好者, 本项目的目的就是依据数独的玩耍规章, 通过对数据结构的分析和人工智能算法的争论, 利用运算机程序来实现对已知数独玩耍的快速求解；1.3 数独出题描述数独玩耍挑战者的水平各异, 对数独题目的难度要求各不相同, 所以本项目致力于设计一种算法, 使其在尽可能短的时间内生成不同难度等级的数独题, 以中意不同水平玩耍者的需求； 同时, 该算法仍要考虑到三个方面要求： 可变化的难度、解的唯独性和算法复杂度最小化；2 功能分析2.1 数独求解数独虽然号称是数学问题 , 但在求解时几乎用不上数学运算方法, 事实上它更像是一种思维
3、方式； 数独玩耍开头后, 要想在空格中填入正确的数字, 先要依据数独玩耍规章对 1-9 分别进行规律判定, 然后选择正确的数字填入空格； 另外, 由于某个格子填入数据时, 有可能仍要对原先已填入的数据进行修正, 所以可以考虑使用递推和回溯搜寻来求解数独问题；2.2 数独出题出题时,要能保证算法生成的数独题具有可变化的难度和唯独解 , 该算法内部应当包含有对数独题的求解和评级功能； 本项目使用了一种基于 “挖洞” 思想的数独题生成算法, 将该算法的设计工作分为评级、 求解和生成三部分工作； 利用随机数显现的概率不同来确定不同的难度, 通过防止重填一个被 “挖去” 的格子,或者回溯到一个曾经无法“
4、挖去”的格子,来降低算法的复杂性；EFIEFNEUGBFNKFMEINGFEJFBNEIFKDNF精品资料欢迎下载2.3 题目储存当用户需要退出却仍没有完成数独题目的解答时,可以选择是否储存当前的求解进度；假如需要, 本系统会帮忙用户将目前未完成的数独题目的解答进度储存起来,以便用户下次使用本系统时,可以连续解答上次未完成的题目；2.4 题目读取用户可以在程序开头运行后,选就读取一道之前储存起来的题目进行解答, 被读取的题目将会显示到程序界面上；3 系统设计3.1 功能结构图本程序主要有数独求解和数独出题两个功能,数独求解包括题目检验、解题和输入输出,数独出题包括答案检验、难度选择、出题和输入
5、输出；EFIEFNEUGBFNKFMEINGFEJFBNEIFKDNF精品资料欢迎下载3.2 业务流程图3.3类图SudokuDlg 类：程序的界面类；Solve 类：实现数独题目求解功能；EFIEFNEUGBFNKFMEINGFEJFBNEIFKDNF精品资料欢迎下载Make类：实现数独题目出题功能；Pre 类：对数据进行预处理；3.4 界面设计3.5 算法设计3.5.1 数独求解算法解决该数独求解问题时的要考虑的主要方面有：判定题目合法性, 即验证给出数据本身是否符合玩耍规章, 行、列以及小九宫中从不重复地显现数字 1-9 ；接受递推算法, 如可以填入数字就填入数字, 并入栈以便回溯, 否
6、就回溯至前面填入数字处重新填数；全部空白处都要填满数据；其中,最重要的就是如何通过递推算法填入正确的数字,或者通过回溯算法重新填入数字并得到最终解,这是本算法的核心内容；回溯法是解决数独问题的有效方法,有着较快的解题速度；然而一般的常用 的回溯算法仍然有不足之处,比如会进行重复的运算；所以在接受回溯法之前, 仍可以利用一点小技巧, 以缩短回溯算法的运行时间, 甚至可将运行时间缩短接近于0；这个小技巧即在回溯算法的基础上,接受有限递推算法进行预处理；算法活动图如下：EFIEFNEUGBFNKFMEINGFEJFBNEIFKDNF精品资料欢迎下载3.5.1数独出题算法要想设计一个算法用以生成各种难
7、度等级的数独题,通过对玩耍规章的分析, 第一从三个方面定义难度等级, 分别是已知格总数、 已知格的分布和穷举搜寻复杂度；本算法接受“挖洞”思想,经过以下步骤生成数独题：用随机算法生成一个数独题目；用求解算法生成终盘；依据难度挖去部分数字；整个生成数独题的算法分为两步执行：先利用拉斯维加斯随机算法随机生成一个填满数字且符合玩耍规章的终盘； 而后依据所需求的难度等级抹去一些数字, 难度等级由随机数显现的概率来准备；算法活动图如下：EFIEFNEUGBFNKFMEINGFEJFBNEIFKDNF精品资料欢迎下载4 系统实现4.1 开发平台本项目基于 VisualStudio 2021 平台的 MFC
8、,接受 C+语言进行开发与测试；4.2 运行环境本项目可在各个版本的 Win7 系统或者 Windows XP系统下运行；4.3 数据结构数据结构是运算机储备、 组织数据的方式； 通常情形下, 细心选择的数据结构可以带来拥有更高的运行或储备效率的算法；一般认为, 一个数据结构是由数据元素依据某种规律联系组织起来的, 对数据元素间规律关系的描述称为数据的规律结构；数据必需在运算机内储备 ,数据的储备结构是数据结构的实现形式, 是其在运算机内的表示；数独从形式上看是一个方阵,特别适合用数组来表示；4.3.1 主要数组本项目中所用到的主要数组有：int sudoku82该数组的用途是储备题目以及储存
9、最终结果, 全部的 99个数字被依次储备在该数组中, 空白处就初始化为 0；之所以把数组范畴设计成 82 而不是 81,是为EFIEFNEUGBFNKFMEINGFEJFBNEIFKDNF精品资料欢迎下载了程序的易读性,使得数组元素的最大下标可达81,下同；int fix82该数组的用途是如 sudoku数组中某位置的数字不为空,就 fix 数组相应位置的元素值为 1,否就为 0,即fix 数组是用来记录哪些位置的数字是已经确定下来的；int possible8210该数组的用途是记录全部未确定数字的全部可能性, possible 数组各元素的值在初始化时被初始化为与其其次维的下标一样,即 0
10、-9 （其中0表示空值）；在中间运算过程中, 如发觉第一维某位置的某种可能性已不复存在, 就将第一维下标是该位置而其次维下标是该不再可能的数字的元素值改为 -1 ；int review82该数组的用途类似于栈, 在回溯算法过程中起到至关重要的作用； 回溯之前, 要把全部 fix 数组中值为 0的位置依次存放进 review 数组；回溯中,由低到高依次逐步确定这些位置的数值,无法确定者（即1-9 的数字都不适合者）就应当回退到前一个位置,并修改其 fix 数组中的值,依次类推,直至review 数组所存放的全部位置的值都能确定（即题目完成） ,或回退到最初点的前一个位置（即题目有误）；4.3.2
11、 相关函数本项目中为实现算法的数据结构所用到的主要函数如下：void setPossible（）该函数是用来设置 possible数组中元素的值,其具体功能是：对于fix数组中每一个值为 0 的位置（即对于每一个没有确定下数字的位置） ,考察其可能的数字是哪些,并记录下来；考察的方法是：在1-9 这些数字中除去在当前行、列、九宫中已有的数字,剩下的即为可能的取值对象；bool fixPossible（）该函数是用来修改 fix 数组和 possible 数组中元素的值,其返回值表示了在此次运行该函数过程中是否执行了修改；其具体功能是：对于fix 数组中每一个值为0的位置（即对于每一个没有确定下
12、数字的位置） ,考察其可能的数字的个数, 如为1,就将fix 数组该位置的值改为 1且sudoku数组该位置的值改为该唯独可能的数字（即该位置的值已确定下来） ,且返回真；如没有只有一种可能性的位置, 就返回假；bool isExist（int i,int j）该函数用于回溯过程中,其用途是：判定 sudoku数组中位置为 i 的元素的值是否可能为 j ,即判定的是位置 i 所在的行、列以及九宫中是否已经存在数字 j , 如存在就返回真,否就返回假；EFIEFNEUGBFNKFMEINGFEJFBNEIFKDNF精品资料欢迎下载4.4 求解算法实现4.4.1 有限递推在执行一次 fixPoss
13、ible函数之后,就可能会确定下一些原先没有确定的数 字,那么此时 possible 数组的值必定也会变动； 这是由于确定下的数字越多, 某些位置的可能数字的数目就会削减,那么此时就应再执行setPossible函数修改possible 数组；而修改之后可能又会显现一些只有一种可能性的位置,那么就应当再执行 fixPossible函数；于是,只要如此循环往复下去,就能最大限度地确 定下依据题目本身含义和规章而确定下的内容；确定的数字越多, 对于将来回溯也就越有利； 体会说明, 有些数独题直接就可以通过执行大约 10多次的有限递推循环体解决； 一般情形下, 有限递推的循环终止只有两种情形： 一是
14、推出了全部结果；二是 fixPossible函数返回值为假,即不存在只有一种可能性的位置；预处理的主要代码见附录；4.4.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函数对栈顶所储存位置的可能显现的数字进 行判定,把遇到的第一个可能数字放进s
