本站原创本文是一篇数据结构论文范文,数据结构有关毕业论文范文,关于数独问题的一种简单解法相关研究生毕业论文开题报告范文。适合数据结构及计算机及参考文献方面的的大学硕士和本科毕业论文以及数据结构相关开题报告范文和职称论文写作参考文献资料下载。
摘 要 ：在计算机解决数独问题的算法中,回溯法是非常有效的.这是一种数据结构简单、算法逻辑清晰、程序简洁明了、运行高速有效的解题方法,并结合源程序与实例进行说明和论述.
关 键 词 ：数独；算法；回溯；穷举；lcc-win32
中图分类号：TP312 文献标识码：A 文章编号：1009-3044（2014）22-5340-05
数独是一种逻辑填数游戏,它起源于瑞士数学家欧拉提出的拉丁方阵.20世纪70年代该游戏在美国兴起,80年代中期开始在日本流行,“数独”（sudoku）一词就源自于日本,在本世纪初数独游戏传入我国,2005年起风靡世界,其热潮至今仍方兴未艾,很多世界著名的报纸都有数独智力题的连载,每年在世界各地都举行各种各样的数独比赛,其中2013年世界数独大赛在中国举行.
1.数独游戏规则
数独是9*9的方阵,其中又可分为9个3*3的九宫格,如图1所示.玩家在方阵中填入1-9之间的数字,保证每一行、每一列、每一个九宫中的数字都不相同,所以数独又可以看作是有宫的9阶拉丁方阵.通常,方阵事先给定一些数字,以便于玩家依据这些初始数字进行填空,而初始数字的多寡与位置,亦一定程度上决定着题目的难易程度以及解是否能够唯一.据推证,最少必须有17个初始数字方可保证题目具有唯一的解.有关数独的详细资料请看参考文献[1].
2.解法
数独可以锻炼人的脑力,玩家可以使用摒除法、余数法等方法来逐步求解.而对使用电脑来计算数独题目的研究也有很多,常用算法有递归法、候选数回溯法、枚举法、遗传算法、方程求解、使用Dancing Link算法等.由于计算机运算速度极快,对于此类有限集合的计算问题,我们可以简单地采用回溯穷举的方法来解题,几乎所有的数独题目都可以迅速地得到结果.该文提出的就是这样一种简洁高效的数独解法,其解决一道数独难题所花时间通常在ms级别.与其它回溯算法相比,本算法采用的数据结构更为简单,逻辑更为清晰.
3.程序结构
程序主体由1个全局二维数组和3个函数构成.
3.1 二维数组Table
该数组为9*9的二维数组,用来存放数独方阵每一个格子的数值.初始化时,它接收来自用户输入的提示数,试探填入数字时,它也是提供比较判断的基础,最后,如果题目有解,输出其中的每一行、每一列的数字.
3.2 函数InputTable
该函数没有输入、输出参数,其功能是输出提示信息,并接受用户输入的数独方阵,每一行的输入类似于“..1.3..7.”的形式,其中“.”（也可以为0或空格）为待填空格,数字为提示数.每一行输入完毕,就初始化二维数组Table对应的行中元素,待填空格对应的单元被初始化为0.如输入其它的内容或输入不符合规则,则退出程序.
3.3 函数Ok
该函数有三个参数：参数m为试探填入的数字,x和y是待填空格在二维数组Table中的位置.函数的功能是检测试探数是否符合数独游戏的规则.如果在同一行、同一列和九宫中没有与m相同的数字,则试探成功函数并返回1,否则失败并返回0.关键点在于计算（x,y）对应的九宫左上角在Table中的位置（x0,y0）,然后循环比较即可.
3.4 函数main
主函数的功能主要完成穷举与回溯等工作.试探时采用的是暴力穷举数字1-9而非候选数的方式.因为如果采用候选数方式,则需要事先对Sp中每一个空格扫描出候选数,用相应的数据结构来储存,这样要增加数据结构；然后在试探时依次从该数据结构中取出候选数,这同样需要时间开销,而逻辑结构和程序也会变得复杂.
函数首先对二维数组Table进行扫描,记录所有待填空格（即值为0的元素）在数组中的位置,保存在数组Sp中,这是一个2*81的数组.该数组是算法的关键,通过此数组我们就把一个图的问题转化为一个线性表的问题.然后是主循环,从Sp数组的起始元素开始进行试探与回溯,当处理完Sp中所有的空格,那么表示得到了问题的解,如果回溯完Sp的起始元素仍旧不行,则表示问题无解.算法描述如图2所示.
4.源程序
6.结束语
数独这种游戏对于锻炼人的逻辑思考能力是大有裨益的,在使用计算机来解决数独问题的算法中,实践证明,该文提出的是一种数据结构简单、算法逻辑清晰、程序简洁明了、运行高速有效的解决方法.