数独实验报告范文
时间:2021-12-19 13:45:11 admin
Sudoku 数独实验报告
一、 算法描述
求解Sudoku让人最容易想到的方法是穷举每个方格可能的值,如果符合条件,则得到解,不符合条件则进行回溯。通过递归的方法,显然可以得到数独的解。
我想到的简单的递归方法,是每一行从左到右,试验每一个方格可能的数字,进行递归。这种方法看似非常麻烦,实际上对于一般的数独题,速度是非常快的,思想比较简单,写出来的代码也非常简单、易懂。
算法1:简单递归方法
从第一个格开始,从1到9试验,是否满足行、列、九宫格互不相同的条件。若满足条件,则填入该数字,再试验下一个格。当一个格子出现没有数字能填的情况时,说明已经填的数字有误,回溯,再进行递归。
算法2:优化的递归算法
先遍历所有格子,统计每种格子可能出现数字的个数。每次挑选可能出现数字个数最少的格子来进行递归。
设置三维数组poss[i][j][k]来存储可能出现数字的信息。poss[i][j][0]记录i行j列的格子可能出现数字的个数,poss[i][j][k](1<=k<=9) 若poss[i][j][k]=1,表示k可能在(i,j)格出现。若poss[i][j][k]=0,表示k不可能在(i,j)格中出现。每次找poss[i][j][0]最小的格子,来进行下一个递归。
算法3:生成数独棋盘的算法
我最开始的想法是穷举法,随机生成满足行各不相同的9行,再判断9宫格、每列是否符合要求,符合条件时,随机生成停止。然而,这种算法的当然时间复杂度显然是过高。第99一步的随机生成的次数是9*9/P9=9608。随机生成一组棋盘耗时就非常大。后来,我从求解的个数的程序获得启发。算法二对于1000多组解的数独棋盘,解起来也很快。随机生成填9个方格,再用算法一的方法解出来,取第一组正确的解作为棋盘即可生成填好的棋盘。再把一定数量的格子的数字随机删除,计算解的个数。如果解唯一,就得到了棋盘。
二、数据结构
这三种算法的数据结构不是非常复杂,只是普通的数组。
算法一:数组a[i][j]
算法二:数组a[i][j]和poss[i][j][k]
算法三:数组a[i][j]和poss[i][j][k]
三、时间效率分析
算法1:这种算法在tsinsen系统上只用了15ms得到全部答案。
虽然这种算法在tsinsen系统的测试中有很好的表现,但是我试了试在几道骨灰级难度的题,发现这种算法可能会用到10秒以上的时间,并且测试数据不同,时间差异非常大。
我认为,这种算法的漏洞在于,如果开始的格子可能出现的数字非常多,递归树开始的枝会非常多。并且,我们一般做数独题,都会先挑可能出现数字个数最少的格子来填,充分利用了已知条件。然而,这种算法只按格子的行列顺序来试验,显然非常傻。于是,我想出了第二种算法。
算法2:这种算法耗时长。
非常令人失望的是,虽然它能在短时间内解出骨灰级题目,但是,和上一个算法相比,对于简单的题目,它比较耗时。在tsinsen系统中测试的时间是91ms。它的缺陷在于,每次递归都必须更新(i,j)格子所在的行、列、九宫格所有的元素。每次要求20个数的poss[i][j]。回溯同样要更新。并且求poss[i][j]的函数时间复杂度是O(n)。每一步所耗时间比上一种算法多很多。但是,总的试验的步数能显著减少。 所以,这种算法适用于数独解题的动画演示和解极难题目。
四、程序结构
五、运行结果
六、总结和反思
后来老师提高了难度,要求程序能求出多解数独题的解的个数。几千个解的数据都能迅速得出答案,但是几万个解的数据,需要很长时间,更别提几百万的数据。这两种递归的算法都有问题,优化的空间也有限,需要更强大、高效的算法。
这次Project让我不断思考,改进了最初的算法。编程是确实是一个克服困难、不断改进与超越的过程。总有新的数据摆在面前,把原来的算法打击得很惨,激励着我们研究更加先进的算法。
结尾:非常感谢大家阅读《数独实验报告范文》,更多精彩内容等着大家,欢迎持续关注学习大全网「Xuexidaquan.Com」,一起成长!
数独实验报告范文相关文章:
★ 羊解剖实验报告
★ 小学科学实验报告
★ 实验报告
【实验报告】推荐文章
1 平放式直流电铃的物理实验报告
2 工业酒精的蒸馏实验报告范文
3 《示波器的的原理和使用》物理实验报告
4 高中化学固态究竟的制取和碘水中碘的萃取实验
5 大物实验报告
6 霉菌实验报告范文
7 关于网络商务信息检索与利用的实验报告范文
8 化学实验报告范例
9 化工原理干燥实验报告
10 板桥镇中心小学科学实验报告
11 大学普通物理实验报告模板
12 兔子心脏采血的实验报告范文
【实验报告】图文精华
-
平面设计实验报告3000字
摘要:实践是检验真理的标准,作为一名即将毕业的学生,在经历了大学三年的理论学习之后,必须接受一段时期的实践。因...
-
销售管理的综合模拟实验报告
实验剧本: 张老板如何与ka打交道实验周期: 4 季度 实验时间:第11周至 第13周 小组名称: 第六小组 练习: 004 小组成员、...
-
高一化学的实验报告范文
实验1 用玻璃杯取高度为h1的常温自来水,然后放在盛有水的平底锅内加热,使杯内水温升高并达到沸点,待冷却至常温后,...
-
水污染综合实验报告
一、实验目的与要求 1. 掌握测试不同废水的色度、浊度、COD、电导、pH等水质指标的分析方法。 2. 增强对污染物综合分析...
-
化工原理干燥实验报告
一、摘要 本实验在了解沸腾流化床干燥器的基本流程及操作方法的基础上,通过沸腾流化床干燥器的实验装置测定干燥速率...
-
初中物理用铅笔做实验报告范文
惯性实验 只用铅笔即可,将铅笔扔出,铅笔离开手之后仍向前运动,说明物体具有惯性。 力可以改变物体的运动状态 只用铅...
-
提高学生英语言语技能的实验报告
一、课题研究的背景和目标 1、问题的提出现在中学英语教学最大的弊病就是学生缺少言语技能。为了改善学生的交际能力,...
-
VFP实验报告
VFP实验报告 学院: 专业: 年级: 姓名: 学号: 实验室号: 计算机号: 实验日期: 年 月 日 指导教师签字: 成绩: 实验...
- 上一篇:科学探究实验与实验报告范文
- 下一篇:化学探究实验报告集锦