论文网
关于数据结构方面论文范文参考文献,与数独问题高效算法的与实现相关论文查重软件
本论文是一篇关于数据结构方面论文查重软件,关于数独问题高效算法的与实现相关学年毕业论文范文。免费优秀的关于数据结构及参考文献及数字方面论文范文资料,适合数据结构论文写作的大学硕士及本科毕业论文开题报告范文和学术职称论文参考文献下载。
摘 要：数独益智游戏（Sudoku）是近年来全球流行的一种智力游戏.本文通过分析数据结构、“非循环判断”预处理算法和回溯算法,深入探讨了数独问题的解决方案,并给出了该方案的实现算法,实验证明该算法是正确高效的.
| 有关论文范文主题研究: | 关于数据结构的论文范文检索 | 大学生适用: | 函授论文、本科论文 |
|---|---|---|---|
| 相关参考文献下载数量: | 14 | 写作解决问题: | 怎么撰写 |
| 毕业论文开题报告: | 文献综述、论文结论 | 职称论文适用: | 期刊目录、中级职称 |
| 所属大学生专业类别: | 怎么撰写 | 论文题目推荐度: | 优质选题 |
关 键 词：数独；非循环判断；算法；回溯法
中图分类号：TP302
“数独”益智游戏（Sudoku）是瑞士数学家欧拉发明的,目前在国内外非常流行.游戏在9*9的单元表格中进行,单元表格不仅被分为9行、9列,也被分为3*3个九宫格.单元表格中已存在若干数字,其余为空格.游戏规则要求玩家在每个空格中填入1～9之间的数字,使每个数字在每行、每列、每个九宫格仅出现一次.国内许多论文对数独游戏的教学意义做了深入讨论,但研究其求解算法的论文不多[1],用计算机进行快速求解的算法更少,参考文献[2]使用“有限递推”预处理提高了算法的执行速度,但其本身每次都要处理
关于数据结构方面论文范文参考文献
1数据结构与回溯法简介
1.1数据结构
精心设计的数据结构可让算法更加高效[5].主要的数据结构是5个整型数组,其中2个一维数组,3个二维数组：
（1）intaResult[81],该数组的用途是接收题目（空白处则初始值为0）以及保存最终结果（所有的9*9个数字按序存储在该数组中）；
（2）intaEmpty[81],该数组记载空白单元表格的序号和试填数字（前2位表示序号,第3位表示数字）,这样既可减少搜索空间又方便下一次试填数字（原试填数字+1）；
（3）intaRow[9][9],该数组标识某行某个数字是否存在,减少判断时间；
（4）intaCol[9][9],该数组标识某列某个数字是否存在,减少判断时间；
（5）intaNine[9][9],该数组标识某九宫格某个数字是否存在,减少判断时间.
1.2回溯法简介
回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标.探索到某一步,发现原先选择并不优或达不到目标时,就退回一步重新选择[6].
2预处理算法
在读取数独问题时用特定数组记载空白单元表格的序号,过滤掉已填数字表格,减少搜索空间；判断某一空格能否填入某一数字时本文采用“非循环判断”预处理算法（一般采用循环判断[2][3]）,该算法思想是：按序扫描问题时,对原有数字进行预处理,即根据该格序号及数字对aRow、aCol和aNine数组进行相应标记,如：第9格（下标从0开始）的数字为5,预处理时该格行号为1、列号为0、九宫格序号为0,结果为：aRow[1][4]等于1,aCol[0][4]等于1,aNine[0][4]等于1,则表明第1行、第0列和第0九宫格不能填数字5.
3算法设计
（1）读入数独问题.
（2）给数组aEmpty、aResult、aRow、aCol和aNine赋初值.
（3）按序扫描问题,把未填数字的空格序号乘以10后存入aEmpty数组,把已填数字或0按序号存入aResult数组,同时根据序号及已经填的数字给aRow、aCol和aNine数组进行预处理.
（4）如果aEmpty数组中存在未填写数字的空格序号,则从aEmpty数组中取出一个未填写数字的空格序号,否则执行（11）.
（5）把取出的空格序号进行行号、列号及九宫格序号分解.
（6）从数字1开始直到数字9尝试填写,并对其行、列及九宫格进行冲突判断,若尝试成功执行（7）,否则执行（8）.
（7）执行相应标识处理后转到（4）.
（8）退回到上一个填数序号,若该填数序号存在则执行相应标识处理后执行（9）,否则执行（12）.
（9）如果原来填写数字的下一个数字存在,对原来填写数字的下一个数字尝试填写.
（10）下一个数字尝试填写成功执行（7）,否则执行（8）.
本篇论文网址 http://www.sxsky.net/benkelunwen/060105240.html
（11）成功找到1个解,退出.
（12）无解,退出.
//关键源代码
voidgetAnswer（inttx）
{
//tx表示未填空格数
while（no { row等于tno/9；//取行序号 col等于tno%9；//取列序号 tno等于aEmpty[no]/10；//取小格序号 bnum等于aEmpty[no]%10；//取小格试填数字 jno等于row/3*3+col/3；//在九宫格中对应的序号 if（rflag等于等于0） { //说明上次未能填数 aResult[tno]等于0； aEmpty[no]等于tno*10； aRow[row][bnum-1]等于0；//标识行 aCol[col][bnum-1]等于0；//标识列 aNine[jno][bnum-1]等于0；//标识九宫格 } rflag等于0；//填数标志//bnum表示小格试填数字 for（num等于bnum+1；num<10；num++） { if（aRow[row][num-1]等于等于1）continue；//判断同行 if（aCol[col][num-1]等于等于1）continue；//判断同列 if（aNine[jno][num-1]等于等于1）continue；//判断九宫格 aResult[tno]等于num；//填数字 aRow[row][num-1]等于1；//标识行 aCol[col][num-1]等于1；//标识列 aNine[jno][num-1]等于1；//标识九宫格 aEmpty[no]等于tno*10+num；//第no个为"序号*10+数字" no++； rflag等于1； break；//填好1个就跳出for循环 } //没有填数 if（no等于等于0） { printf（"NoAnswer＼n"）； break； } elseif（rflag等于等于0） { no--；//返回上一数重填 } } } 4实例测试 前3个实例取自参考文献[2],第4个实例出自芬兰数学家因卡拉[4]： 下面是对上述4题各计算5次的时间测试结果（在操作系统xp和CPU为AMD4600+（2.4G）的环境下测试的）：从上面结果可知,一般的数独难题（包括号称世界上迄今难度最大的数独游戏）可在15ms内找出答案；由此可见,本算法是高效的；通过检验本算法所给答案也是正确的. 参考文献： [1]王琼,邹晟.数独问题的求解、评价与生成算法的研究[J].南京师范大学学报（工程技术版）,2010,10（1）：76-79. [2]雷蕾,沈富可.关于数独问题的算法的设计与实现[J].电脑知识与技术,2007,2（2）：481-482. [3]李盘荣.“数独”游戏的算法研究与实现[J].电脑知识与技术,2008,3（8）：1715-1717. [4]http：//hb.sina../news/sh/2013-05-26/144777326.. & 关于数据结构方面论文范文参考文献,与数独问题高效算法的与实现相关论文查重软件参考文献资料：
