毕业设计（论文）开题报告：数独问题的设计算法研究

PAGEPAGE8毕业设计（论文）开题报告题目数独问题的设计算法研究专业信息与计算科学姓名班级学号指导教师提交时间一、综述本课题的研究动态，说明选题的依据和意义1、本课题研究动态1.1数独研究背景数独是一种源自18世纪末的瑞士，后在美国发展、并在日本得以发扬光大的数字谜题。世界数独锦标赛是世界上规模最大的数独比赛，由世界智力谜题联合会主办。首届世界数独锦标赛于2006年在意大利的卢卡举办，以后每年举办一届。2013年第八届世界数独锦标赛在中国的北京举行。1.2数独玩法数独盘面是个九宫，每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件，利用逻辑和推理，在其他的空格上填入1-9的数字，使1-9每个数字在每一行、每一列和每一宫中都只出现一次。1.3数独的发展历程早在数千年前，中国人就发明了九宫图：在9个方格中，横行和竖行的数字总和是相同的。“数独”也不是什么新生事物，已经存在了数百年。现今流行的数独于1984年由日本游戏杂志《パズル通信ニコリ》发表并得了现时的名称。数独本是“独立的数字”的省略，因为每一个方格都填上一个非零的个位数。18世纪，瑞士数学家莱昂哈德·欧勒发明了“拉丁方块”，但并没有受到人们的重视。直到20世纪70年代，美国杂志才以“数字拼图”的名称将它重新推出。日本随后接受并推广了这种游戏，并且将它改名为“数独”，大致的意思是“独个的数字”或“只出现一次的数字”。1.4数独近现代发展成就自二十一世纪以来，数独进入了高速发展期，尤其是计算机的快速发展带动了数独设计以及计算的多元化。还有学者发表了一些研究，如：宋韬在文献[11]中根据常规数独问题的基本规则，推导了五项数独求解基础方法,然后结合计算机程序的实现，将其设计为可各自独立执行的算法。在此基础上，以人工求解数独问题的思维过程为依据，提出了基于策略模式的数独优化求解算法。该算法实现了在数独问题的初步推断和后续回溯法求解过程中根据各单元格出现的不同数值情况自主判定并选择执行不同的策略，从而通过较少的运算量将未知情况数量降至最小，提高了计算机求解数独的运算效率。其中杨晓华教授在文献[10]中用C语言模拟数独的人工解题思路，用计算机模拟人脑解题的方法，提出了数独问题人工解法程序实现的可能途径，介绍了唯一法、排除法及回溯法三种解题方法。有利于学习C语言及相应的编程技巧，尝试着把人的思维方式转化成相应的计算机程序，便于人工智能方面的研究。柯春梅教授在文献[6]中本文首先从标准数独的条件与规则出发，引入三元0-1变量,建立标准数独的0-1整数规划模型,根据模型设计LINGO求解程序，用一个数独难题进行验证，说明程序计算的准确性；然后将标准数独的LINGO求解程序推广到窗口数独、额外区域数独、奇偶数独等三种变形数独的求解；最后利用数独联盟五段段位考试训练题进行验证，运算时间不超过2秒，准确率达到100%，说明这些LINGO程序求解数独问题,速度快且结果准确可靠。2、选题的依据和意义2.1数独对近现代的影响在中国北京有80多所中小学把数独作为校本课程引进课堂；东莞市也有10多家学校在学校开设了数独第二课堂，40多家学校开过数独公开课。数独的魅力可不仅仅局限于中国：牛津大学为它举办程序设计大赛，瑞士银行将它列入招聘员工试题；国际大学生建模大赛将它列为赛事选题。英国、日本等政府把“数独”引进学校课堂，影响数独难度的因素很多，就题目本身而言，包括最高难度的技巧、各种技巧所用次数、是否有隐藏及隐藏的深度及广度的技巧组合、当前盘面可逻辑推导出的出数个数等等。数独冲出日本成为英国当下的流行游戏，得归功于曾任香港高等法院法官的高乐德（WayneGould）。2004年，他在日本旅行的时候，发现杂志上介绍的这款游戏，便带回伦敦向《泰晤士报》推介并获得接纳。英国《每日邮报》也于三日后开始连载，使数独在英国正式掀起热潮。数独不仅是报章增加销量的法宝，脑筋动得快的《泰晤士报》还做起手机族的生意，花4.5英镑就能下载10则数独游戏到手机上玩。渐渐，其他国家和地区受其影响也开始风靡数独。2.2数独与生俱来的独特魅力与同类似的填字游戏不同，数独受欢迎的原因之一是它既不需要丰富的百科知识，也不要掌握大量的词汇，这使其能迅速为孩子和初学者所接受。根据游戏开始时的方格中已有的数字和位置，数独难易程度不同，有些复杂的甚至令数学家也不能完成。据著名的动游戏开发商AstrawareLtd.预计，移动数独游戏的版本多达几十种，Palm和WindowsMobile设备版本的数独游戏就各有20种左右。Sudokumo推出的移动数独游戏，能够下载到大多数手机中。这家位于英国的游戏软件公司表示，已经在全球卖出了7500套数独游戏，而且来自用户的兴趣还在增加。数独游戏由数学家欧拉发明,目前在国内外非常流行。通过对数独求解及分析，归纳总结出一套有效的求解算法——整数规划法,以计算机直接模拟人脑的思维方式,逐个排除不可能出现在宫格中的数字。因为数独不仅有趣好玩，还可以增进玩者的推理与逻辑能力，这种游戏全面考验做题者观察能力和推理能力，虽然玩法简单，但数字排列方式却千变万化，所以不少教育者认为数独是训练头脑的绝佳方式。二、本课题研究的基本内容，拟解决的主要问题和难点问题1、基本内容本课题研究如何设计数独问题，探讨数独设计问题的算法并编程实现。在此过程中需要了解数独问题的由来，数独问题的介绍及各种数独问题设计的方法，并利用Matlab作为编程软件，编写出程序并正确运行。本课题研究的数独问题所采用的方式便是利用Matlab实现数独游戏的设计，该程序能够设置不同难度等级，实现数独游戏设计的多样化。设计后通过测试来检验界面操作、数独唯一解和数独功能的完整性。为确保设计能够执行相应的功能并且存在唯一解，可采取以下设计方法：1.唯一解法2.允许数标注法3.已知数标线法4.回溯法其中在编写数独设计程序时可以考虑人工智能的设计方法。所谓人工智能设计应当是设计者对该游戏的特性有较为深入的了解依据其内在联系设计出的和人类思维相似的解决算法。目的是为了能够提供更快的更准确的设计方法。2、拟解决的主要问题（1）数独问题的由来、数独问题的介绍；（2）数独问题研究的意义；（2）数独问题的终盘的设计方法；（3）数独问题的一般设计方法讨论；（4）数独问题的（分初级、中级、高级、特级等级别）设计及其编程实现；（6）数独问题的研究成果及未来展望。3、难点问题（1）特型数独问题的设计及其编程实现；（2）额外区域数独问题的设计及其编程实现。三、研究步骤、方法及措施1、了解基本课题，阅读与课题相关的各类文献，会基本数独解法；1.1被筛选数标线法算法目的数就是要在某空格填的数.所谓“目的数标线法”,就是从某一个预想的目的数出发引出标线，把这些标线集中到某宫、某行、某列，然后在其中排除不允许该目的数存在的格子，而将目的数落实到正确的格子中。1.2回溯法回溯法是一种搜索算法，其基本思路是：在一个问题中，根据题意给出的边界条件划定出所有可能解的范围（称为可能解），根据题意确定出约束条件.利用程序顺次在所有可能解中，根据题意确定出约束条件.利用程序顺次在所有可能解中，搜索时按照深度搜索的方式进行.即在第一层选定一个满足约束条件的解，然后以该可能解为出发点，搜索第二层的一个可能解（试探）.如果搜索到第二层的一个可能解，则继续搜索第三层的一个可能解.依次类推，直到所有层的可能解被找到，则得到了该问题的一个完整解.如果第二层所有的可能解都不满足约束条件，则返回第一层，放弃原有的可能解，使用第一层的下一个可能解（回溯）.以此类推，寻找第二层的一个可能解。1.3唯一解法当某行已填数字的宫格达到8个，那么该行剩余宫格能填的数字就只剩下那么还没出现过的数字了，成为行唯一解。同理，当某列或某宫已填数字达到八个，那么剩余数字只剩下未出现的那个。2、了解数独问题的各类设计方法，学习Matlab软件编程及其他有关的知识点；2.1总体思路先得到一个完整数独。然后根据难度需要，有选择性的的挖出一些空格来，判断是否符合条件以及游戏规则，最后选择输出。2.2过程分析第一行：取1`9个数字，打乱后放入第一行的每个格子里。第二行：由于第一行的限制，这时每个格子的数字可选择一个专门的函数来确认。从第一列开始直至第九列结束。数字生成好后，游戏时随机的把部分数字遮盖住以此生成空格，判断填入正确与否。3、研究各章数独问题的设计方法，并对每种算法的效率作比较；下面一道2013年中国锦标赛数独题目000,009,002;129,000,000;000,207,003;015,030,090;090,040,020;040,070,380;700,503,000;000,000,548;500,100,000在使用MATLAB软件可以得出，回溯法算法求出此问题需要进行0.182482秒，整数规划法求出此问题需要进行2.994893秒，而被筛选数标线法算法求出此问题需要进行0.291465秒。由此可见回溯法解题效率最高，整数规划法要比回溯法低一些，并且这个差距会随着题目难度的增加而增加。在正文中会具体介绍到。4、设计实验方案，做出实验；5、分析实验结果，得出结论。四、工作进度序号设计（论文）各阶段名称日期1查阅数独问题的资料（网上资料或图书馆资源），熟悉数独问题和数独游戏的玩法。1～2周2理解数独问题的基本设计方法，熟悉Matlab编程软件。2～3周3毕业实习，撰写文献综述，开题报告。3～5周4数独问题的终盘的设计方法及其编程实现。5～7周5数独问题的(分初级、中级、高级、特级等级别)设计及其编程实现。18～12周6特型数独问题的设计及其编程实现，额外区域数独问题的设计及其编程实现。12～14周7进行论文写作，完成相应计算机程序的设计。14～15周8完善软件、完成毕业论文。16周总结及未来展望影响数独难度的因素很多，就题目本身而言，包括最高难度的技巧、各种技巧所用次数、是否有隐藏及隐藏的深度及广度的技巧组合、当前盘面可逻辑推导出的出数个数等等。对于玩家而言，了解的技巧数量、熟练程度、观察力自然也影响对一道题的难度判断。同时由于数独的独特魅力所在，由数独引出的其他游戏也吸引了大量玩家，也有众多的拥护者，而且与数独有千丝万缕的关系，比如：数和（Kakuro）数图（Nonograms/Griddlers）数回（SlitherLink）数墙（Nurikabe）数连（NumberLink）数独爱好者同样不能错过这些优秀的逻辑推理游戏。数独是一种人生，它不允许你填错一个数字，否则全盘皆输！望着全盘的数字，你不知道哪错了，却不允许你去涂改，只能重新开始！这就跟我们的学习一样，它要求我们要想好再去做，一步一个脚印，确定是那个数字我们才能下手！每个数字都各司其职，都会有他们并不固定的岗位，有可能我在角落，也有可能我在中间，哪里需要我，我就会出现在哪！这就要求我们要注意到上下左右以及这小宫格各方面的协调！是的我们要有大局观！喜欢数独的理由无数种，因为真相只有一个！最后再说几句：生活和做数独一样，不要轻易放弃。当你推断到自以为山穷水尽时,再用1-9的顺序扫一遍,说不定就会有峰回路转的发现。数独的真正魅力就在于看似简单却蕴含了很多不平凡的奥妙。恰恰人生也正像这样一场游戏，在简单的规则中不断挑战自我，专注地生活。最后我衷心的希望每个人都能从数独的游戏中感悟人生的道理，能在知识的海洋里遨游感受数学，感受数独的乐趣。六、主要参考文献[1]商文喜,蔚承建,王开,刘凯.数独问题的一个分布式物理博弈求解[J].计算机应用与软件,2014,31(12):113-115.

[2]黄祖贤.数独游戏的问题生成及求解算法优化[J].安徽工业大学学报(自然科学版),2015,32(02):187-191.

[3]雷蕾,沈富可.关于数独问题的算法的设计与实现[J].电脑知识与技术(学术交流),2007,14(02):481-482+523.

[4]王琼,邹晟.数独问题的求解、评价与生成算法的研究[J].南京师范大学学报(工程技术版),2010,10(01