开题报告-数独问题的设计算法研究.docVIP

一、综述本课题的研究动态，说明选题的依据和意义 1、18世纪末的瑞士，后在美国发展、并在日本得以发扬光 大的数字谜题。世界数独锦标赛是世界上规模最大的数独比赛，由世界智力谜题联合会主办。首届世界数独锦标赛于2006年在意大利的卢卡举办，以后每年举办一届。2013年第八届世界数独锦标赛在中国的北京举行。 1.2数独玩法 数独盘面是个九宫，每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件，利用逻辑和推理，在其他的空格上填入1-9的数字，使1-9每个数字在每一行、每一列和每一宫中都只出现一次。 1.3数独的发展历程 早在数千年前，中国人就发明了九宫图：在9个方格中，横行和竖行的数字总和是相同的。“数独”也不是什么新生事物，已经存在了数百年。现今流行的数独于1984年由日本游戏杂志《パズル通信ニコリ》发表并得了现时的名称。数独本是“独立的数字”的省略，因为每一个方格都填上一个非零的个位数。 18世纪，瑞士数学家莱昂哈德·欧勒发明了“拉丁方块”，但并没有受到人们的重视。直到20世纪70年代，美国杂志才以“数字拼图”的名称将它重新推出。日本随后接受并推广了这种游戏，并且将它改名为“数独”，大致的意思是“独个的数字”或“只出现一次的数字”。[11]中根据常规数独问题的基本规则推导了五项数独求解基础方法,然后结合计算机程序的实现将其设计为可各自独立执行的算法。在此基础上以人工求解数独问题的思维过程为依据提出了基于策略模式的数独优化求解算法。该算法实现了在数独问题的初步推断和后续回溯法求解过程中根据各单元格出现的不同数值情况自主判定并选择执行不同的策略从而通过较少的运算量将未知情况数量降至最小提高了计算机求解数独的运算效率。 用C语言模拟数独的人工解题思路用计算机模拟人脑解题的方法提出了数独问题人工解法程序实现的可能途径介绍了唯一法、排除法及回溯法三种解题方法。有利于学习C语言及相应的编程技巧尝试着把人的思维方式转化成相应的计算机程序便于人工智能方面的研究。本文首先从标准数独的条件与规则出发引入三元0-1变量,建立标准数独的0-1整数规划模型,根据模型设计LINGO求解程序用一个数独难题进行验证说明程序计算的准确性然后将标准数独的LINGO求解程序推广到窗口数独、额外区域数独、奇偶数独等三种变形数独的求解最后利用数独联盟五段段位考试训练题进行验证运算时间不超过2秒准确率达到100%说明这些LINGO程序求解数独问题,速度快且结果准确可靠。 2、80多所中小学把数独作为校本课程引进课堂；东莞市也有10多家学校在学校开设了数独第二课堂，40多家学校开过数独公开课。 数独的魅力可不仅仅局限于中国：牛津大学为它举办程序设计大赛，瑞士银行将它列入招聘员工试题；国际大学生建模大赛将它列为赛事选题。英国、日本等政府把“数独”引进学校课堂，影响数独难度的因素很多，就题目本身而言，包括最高难度的技巧、各种技巧所用次数、是否有隐藏及隐藏的深度及广度的技巧组合、当前盘面可逻辑推导出的出数个数等等。数独冲出日本成为英国当下的流行游戏，得归功于曾任香港高等法院法官的高乐德（Wayne Gould）。2004年，他在日本旅行的时候，发现杂志上介绍的这款游戏，便带回伦敦向《泰晤士报》推介并获得接纳。英国《每日邮报》也于三日后开始连载，使数独在英国正式掀起热潮。数独不仅是报章增加销量的法宝，脑筋动得快的《泰晤士报》还做起手机族的生意，花4.5英镑就能下载10则数独游戏到手机上玩。渐渐，其他国家和地区受其影响也开始风靡数独。 同类似的填字游戏不同，数独受欢迎的原因之一是它既不需要丰富的百科知识，也不要掌握大量的词汇，这使其能迅速为孩子和初学者所接受。根据游戏开始时的方格中已有的数字和位置，数独难易程度不同，有些复杂的甚至令数学家也不能完成。据著名的动游戏开发商Astraware Ltd.预计，移动数独游戏的版本多达几十种，Palm和Windows Mobile设备版本的数独游戏就各有20种左右。Sudokumo推出的移动数独游戏，能够下载到大多数手机中。这家位于英国的游戏软件公司表示，已经在全球卖出了7500套数独游戏，而且来自用户的兴趣还在增加。1、Matlab作为编程软件，编写出程序并正确运行。本课题研究的数独问题所采用的方式便是利用Matlab实现数独游戏的设计，该程序能够设置不同难度等级，实现数独游戏设计的多样化。设计后通过测试来检验界面操作、数独唯一解和数独功能的完整性。为确保设计能够执行相应的功能并且存在唯一解，可采取以下设计方法： 1.唯一解法 2.允许数标注法 3.已知数标线法 4.回溯法 其中在编写数独设计程序时可以考虑人工智能的设计方法。所谓人工智能设计应当是设计者对该游戏的特性有较为深入的了解依据其内在联系设计出的和人类思维相似