毕业设计（论文）文献综述：数独问题的设计算法研究

本科毕业设计本科毕业设计（文献综述）课题名称：数独问题的设计算法研究专业：信息与计算科学姓名：学号：指导教师：数理学院年月PAGE4摘要数独（sudoku）是一种逻辑性的数字填充游戏，玩家须以数字填进每一格，而每行、每列和每个宫（即3x3的大格）有齐1至9所有数字。游戏设计者会提供一部份的数字，使谜题只有一个答案。一个已解答的数独其实是一种多了宫的限制的拉丁因为同一个数字不可能在同一行、列或宫中出现多于次。在熊伟教授的《数独问题解决》中明确提到：21世纪的数独对人智力的提升尤为重要，对少年儿童逻辑训练的作用主要体现在以下几个方面：逻辑推理能力，使之从小便懂得一步一个脚印地做事才不会或少跌跟头；全方位思考问题能力，这对杜绝片面看问题和偏激情绪很有帮助；耐心攻关能力，以便长大后可以应付各种人生和事业上的艰难险阻。总之，数独游戏是少年儿童的逻辑性、领导力、攻坚心的最理想的训练手段。本文主要研究数独的基本理论，介绍数独设计的应用，并举例说明。关键词：1.数独2.数独设计3.优良性AbstractSudoku(sudoku)isakindoflogicaldigitalfillinggame,playersmustbeindigitalfillineachcase,andeachrow,eachcolumnandeachpalace(i.e.,3x3grid)aretogetheralltheNumbers1to9.GamedesignerswillprovidepartNumbers,thepuzzleisonlyoneanswer.OnehastosolvesudokuisactuallyamuchpalacelimitofLatinsquare,forthesamenumbercan'tbeinthesamerow,columnorpalaceappearmorethanonce.Sudokuinthe21stcenturyisespeciallyimportanttothepromotionofhumanintelligence,logicaltrainingforthechildren'sfunctionmainlyreflectsinthefollowingaspects:(1)logicalreasoningability,fromurinateknowonestepafootprintdon'tdothingsorlittlestumble;(2)thecomprehensivethinkingability,toputanendtothisone-sidedseeaproblemisveryhelpfulandextremeemotions;(3)thepatientresearchability,sothatwhenIgrowupcancopewithvariousdifficultiesandobstaclesonthelifeandcareer.Tosumup,thechildrenofsudokulogic,leadership,toovercometheheartoftheidealmethodsoftraining.Party'sbasictheory,thisarticlemainlyresearchsudokuintroducestheapplicationofsudokuisdesigned,andanexample.

Keywords:1.Sudoku2.Sudokudesign3.Excellent目录TOC\o"1-3"\u一、研究背景4国内外研究现状4研究内容和方法5总结5五、参考文献5一、研究背景1.1研究目的数独是一种源自18世纪末的瑞士，后在美国发展、并在日本得以发扬光大的数字谜题。世界数独锦标赛是世界上规模最大的数独比赛，由世界智力谜题联合会主办。首届世界数独锦标赛于2006年在意大利的卢卡举办，以后每年举办一届。2013年第八届世界数独锦标赛在中国的北京举行。早在数千年前，中国人就发明了九宫图：在9个方格中，横行和竖行的数字总和是相同的。“数独”也不是什么新生事物，已经存在了数百年。现今流行的数独于1984年由日本游戏杂志《パズル通信ニコリ》发表并得了现时的名称。数独本是“独立的数字”的省略，因为每一个方格都填上一个非零的个位数。18世纪，瑞士数学家莱昂哈德·欧勒发明了“拉丁方块”，但并没有受到人们的重视。直到20世纪70年代，美国杂志才以“数字拼图”的名称将它重新推出。日本随后接受并推广了这种游戏，并且将它改名为“数独”，大致的意思是“独个的数字”或“只出现一次的数字”。国内外研究现状自二十一世纪以来，数独进入了高速发展期，尤其是计算机的快速发展带动了数独设计以及计算的多元化。还有学者发表了一些研究，如：宋韬在文献[11]中根据常规数独问题的基本规则，推导了五项数独求解基础方法,然后结合计算机程序的实现，将其设计为可各自独立执行的算法。在此基础上，以人工求解数独问题的思维过程为依据，提出了基于策略模式的数独优化求解算法。该算法实现了在数独问题的初步推断和后续回溯法求解过程中根据各单元格出现的不同数值情况自主判定并选择执行不同的策略，从而通过较少的运算量将未知情况数量降至最小，提高了计算机求解数独的运算效率。其中杨晓华教授在文献[10]中用C语言模拟数独的人工解题思路，用计算机模拟人脑解题的方法，提出了数独问题人工解法程序实现的可能途径，介绍了唯一法、排除法及回溯法三种解题方法。有利于学习C语言及相应的编程技巧，尝试着把人的思维方式转化成相应的计算机程序，便于人工智能方面的研究。数独的魅力可不仅仅局限于中国：牛津大学为它举办程序设计大赛，瑞士银行将它列入招聘员工试题；国际大学生建模大赛将它列为赛事选题。英国、日本等政府把“数独”引进学校课堂，影响数独难度的因素很多，就题目本身而言，包括最高难度的技巧、各种技巧所用次数、是否有隐藏及隐藏的深度及广度的技巧组合、当前盘面可逻辑推导出的出数个数等等。柯春梅教授在文献[6]中本文首先从标准数独的条件与规则出发，引入三元0-1变量,建立标准数独的0-1整数规划模型,根据模型设计LINGO求解程序，用一个数独难题进行验证，说明程序计算的准确性；然后将标准数独的LINGO求解程序推广到窗口数独、额外区域数独、奇偶数独等三种变形数独的求解；最后利用数独联盟五段段位考试训练题进行验证，运算时间不超过2秒，准确率达到100%，说明这些LINGO程序求解数独问题,速度快且结果准确可靠。研究内容和方法李晓辉教授在《数独方设计及其优良性》中有明确提到研究数独的设计方法就是要了解数独问题的由来，数独问题的介绍及各种数独问题设计的方法，并利用Matlab作为编程软件，编写出程序并正确运行。因此本课题研究如何设计数独问题，探讨数独设计问题的算法并编程实现。在本文中研究的数独问题所采用的方式便是利用Matlab实现数独游戏的设计，该程序能够设置不同难度等级，实现数独游戏设计的多样化。设计后通过测试来检验界面操作、数独唯一解和数独功能的完整性。其中在编写数独设计程序时可以考虑人工智能的设计方法。所谓人工智能设计应当是设计者对该游戏的特性有较为深入的了解依据其内在联系设计出的和人类思维相似的解决算法。目的是为了能够提供更快的更准确的设计方法。总结黄裕龙教授《数独之最少提示数研究》中说明：影响数独难度的因素很多，就题目本身而言，包括最高难度的技巧、各种技巧所用次数、是否有隐藏及隐藏的深度及广度的技巧组合、当前盘面可逻辑推导出的出数个数等等。对于玩家而言，了解的技巧数量、熟练程度、观察力自然也影响对一道题的难度判断。同时由于数独的独特魅力所在，由数独引出的其他游戏也吸引了大量玩家，也有众多的拥护者，而且与数独有千丝万缕的关系，比如：数和（Kakuro）数图（Nonograms/Griddlers）数回（SlitherLink）数墙（Nurikabe）数连（NumberLink）数独爱好者同样不能错过这些优秀的逻辑推理游戏。五、参考文献[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):76-79.

[5]肖华勇,田铮,马雷.数独基于规则的逐步枚举算法设计[J].计算机工程与设计,2010,31(05):1035-1037+1113.[6]柯春梅.数独的数学模型与LINGO求解程序[J].长春师范大学学报,2016,35(12):8-13.[7]黄皓.数独问题的一种简单解法[J].电脑知识与技术,2014,10(22):5340-5344.[8]姜华林.数独问题高效算法的研究与实现[J].计算机光盘软件与应用,2013,16(12):82-83.[9]胡英武.数独问题的整数规划模型[J].金华职业技术学院学报,2011,11(03):86-88.[10]杨晓华.数独问题在C语言中的模拟算法[J].电子测试,2015,