人工智能项目建议书.docx
《人工智能项目建议书.docx》由会员分享,可在线阅读,更多相关《人工智能项目建议书.docx(8页珍藏版)》请在咨信网上搜索。
1、项目建议书项目名称:数独游戏出题与求解设计组 员: 李鹏程、吴渊9:38九日目录一项目说明21.1 整体描述21.2出题设计21.3求解设计2二解决方案22.1 项目分析22.2求解方案32.3 出题方案32.4求解方案42.5 开发平台42.6 数据结构42.6.1 主要数组42.6.2 主要函数52.7 求解算法设计62.7.1 有限递推62.7.2 回溯62.8 出题算法设计72.8.1 生成终盘72.8.2 挖洞算法7三方案检测8四项目安排9参 考 文 献9一项目说明1.1 整体描述数独游戏是一种数学方面的游戏,直观上更像一种拼图游戏,其游戏规则是:在99的大九宫格内,已给定若干数字,
2、其他宫位留白,玩家需自己按照逻辑推敲出剩下的空格里是什么数字;必须满足的条件:每一行与每一列都有1到9的数字,每个小九宫格里也有1到9的数字,并且一个数字在每行、每列及每个小九宫格里只能出现一次,既不能重复也不能少;每个数独游戏都可根据给定的数字为线索,推算解答出来。 1.2出题设计本项目计划设计一种算法,在短时间内生成数独题且难度等级不一致,以满足不同水平游戏者的需求。数独游戏挑战者的水平各异,对数独题目的难度要求各不相同,但是有三个方面需要注意:可变化的难度、解的唯一性和算法复杂度最小化。 1。3求解设计 本项目的目的就是按照数独游戏的规则,综合运用数据结构的分析和人工智能的算法,利用计算
3、机程序来实现对已知数独游戏的快速求解。二解决方案2.1 项目分析数独虽然号称是数学问题, 但在求解时几乎用不上数学运算方法,事实上它更像是一种思维方式。数独游戏开始后,要想在空格中填入正确的数字,先要根据数独游戏规则对1-9分别进行逻辑判断,然后选择正确的数字填入空格。另外,由于某个格子填入数据时,有可能还要对原来已填入的数据进行修正,所以可以考虑使用递推和回溯搜索来求解数独问题。出题时,要能保证算法生成的数独题具有可变化的难度和唯一解,该算法内部应该包含有对数独题的求解和评级功能。本项目使用了一种基于“挖洞”思想的数独题生成算法,将该算法的设计工作分为评级、求解和生成三部分工作。首先,根据游
4、戏者需要的难度等级,我们从已知格的总数和分布以及穷举求解的搜索次数这三个方面特性,通过赋权求和来评估一个数独题的难度等级。然后,运用反证法思想,并结合深度优先搜索求解器一起论证一个“洞”被“挖去”后是否能保证该题有唯一解。最后,通过避免重填一个被“挖去”的格子,或者回溯到一个曾经无法“挖去”的格子,来降低算法的复杂性。2。2求解方案 解决该数独求解问题时的要考虑的主要方面有: 从界面或文本读取数独游戏数据; 判断题目合法性,即验证给出数据本身是否符合游戏规则,行、列以及小九宫中从不重复地出现数字19; 逐个取得空白处; 采用递推算法,若可以填入数字则填入数字,并入栈以便回溯,否则回溯至前面填入
5、数字处重新填数; 所有空白处都要填满数据; 输出结果至屏幕或文件.如此看来,最需要仔细考虑的就是如何通过递推算法填入正确的数字,或者通过回溯算法重新填入数字并得到最终解,这个也就是本项目算法的核心,同时也是解题的关键.2.3 出题方案要想设计一个算法用以生成各种难度等级的数独题,通过对游戏规则的分析,首先从以下三个方面定义难度等级:已知格总数、已知格的分布和穷举搜索复杂度。本算法采用“挖洞”思想,经过以下两步生成数独题:运用拉斯维加斯随机算法生成一个终盘;根据所需要的难度等级选取一种挖洞顺序;制定两个约束来控制已知格的分布;通过深度优先搜索来求解,从而保证“挖去”一个数字后该数独题仍有唯一解;
6、引入剪枝技术来避免无效的“挖洞”尝试;对“挖好洞”的数独题进行等效对称变换,以提高游戏题目的多样性。2。4求解方案利用递推和回溯法完成数独问题求解功能;利用拉斯维加斯随机算法、深度优先搜索和剪枝技术完成数度问题出题功能;完成界面良好的数独游戏程序.2.5 开发平台本项目基于Visual Studio 2010平台的MFC,采用C+语言进行开发与测试.2。6 数据结构通常情况下,精心选择的数据结构可以带来拥有更高的运行或存储效率的算法.一般认为,一个数据结构是由数据元素依据某种逻辑联系组织起来的,对数据元素间逻辑关系的描述称为数据的逻辑结构;数据必须在计算机内存储, 数据的存储结构是数据结构的实
7、现形式, 是其在计算机内的表示。数独从形式上看是一个方阵, 十分适合用数组来表示。2.6.1 主要数组本项目中所用到的主要数组有:int sudoku82该数组的用途是存储题目以及保存最终结果,所有的99个数字被依次存储在该数组中,空白处则初始化为0。之所以把数组范围设计成82 而不是81,是为了程序的易读性,使得数组元素的最大下标可达81,下同.int fix82 该数组的用途是若sudoku数组中某位置的数字不为空,则fix数组相应位置的元素值为1,否则为0,即fix数组是用来记录哪些位置的数字是已经确定下来的。int possible8210该数组的用途是记录所有未确定数字的所有可能性,
8、possible数组各元素的值在初始化时被初始化为与其第二维的下标一致,即0-9(其中0表示空值);在中间计算过程中,若发现第一维某位置的某种可能性已不复存在,则将第一维下标是该位置而第二维下标是该不再可能的数字的元素值改为-1。int review82该数组的用途类似于栈,在回溯算法过程中起到至关重要的作用.回溯之前,要把所有fix数组中值为0的位置依次存放进review数组;回溯中,由低到高依次逐渐确定这些位置的数值,无法确定者(即19的数字都不适合者)则应当回退到前一个位置,并修改其fix数组中的值,依次类推,直至review数组所存放的所有位置的值都能确定(即题目完成),或回退到最初点
9、的前一个位置(即题目有误)。2.6。2 主要函数本项目中为实现算法的数据结构所用到的主要函数如下:void setPossible()该函数是用来设置possible数组中元素的值,其具体功能是:对于fix数组中每一个值为0的位置(即对于每一个没有确定下数字的位置),考察其可能的数字是哪些,并记录下来。考察的方法是:在1-9这些数字中除去在当前行、列、九宫中已有的数字,剩下的即为可能的取值对象。bool fixPossible()该函数是用来修改fix数组和possible数组中元素的值,其返回值表示了在此次运行该函数过程中是否执行了修改。其具体功能是:对于fix数组中每一个值为0的位置(即对
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 人工智能 项目 建议书
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【精****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【精****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。