数独实验报告范文
发布时间：2020-03-19
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让我不断思考，改进了最初的算法。编程是确实是一个克服困难、不断改进与超越的过程。总有新的数据摆在面前，把原来的算法打击得很惨，激励着我们研究更加先进的算法。
数独实验报告范文 相关内容:
危机的石头实验为能级的存在提供了直接的证据，对玻尔的原子理论是一个有力支持，那么，下面是第一范文网小编给大家整理收集的弗兰克赫兹实验报告内容，供大家阅读参考。...
初中化学实验报告如何写?下面是第一范文网小编给大家整理收集的初中化学实验报告的相关模板，仅供参考。初中化学实验报告1实验名称 组装实验室制取氧气的装置实验目的 正确地组装一套实验室制取氧气的装置，并做好排水集气的准备实验器材...
本科生实验报告格式及相关要求填写说明1、 适用于本科生所有的实验报告(印制实验报告册除外)；2、 专业填写为专业全称，有专业方向的用小括号标明；3、 格式要求：① 用A4纸双面打印(封面双面打印)或在A4大小纸上用蓝黑色水笔书写。...
大学物理实验报告模板实验报告一.预习报告1.简要原理2.注意事项二.实验目的三.实验器材四.实验原理五.实验内容、步骤六.实验数据记录与处理七.实验结果分析以及实验心得八.原始数据记录栏(最后一页)把实验的目的、方法、过程、结果等记录...
一、实验目的1、了解局域网的组网方式以及双绞线的两种制作规范； 2、掌握RJ－45水晶头的制作，以及网线连通性的测试。二、实验环境RJ－45水晶头若干、双绞线若干米、压线钳一把、测线仪一套。...
一、背景作业场所的合理采光与照明，对生产中的效率、卫生和安全都有重要的意义。它是工作场所设计中的重要项目，无论是天然采光还是人工照明，其主要目的都是给人们的生活和生产提供必需的视觉条件。...
一、问题的提出长期以来，我国中学外语教学效果不理想。学生从初中开始上外语课，上几 学期外语课之后就迅速地产生 了对外语课的厌烦情绪，即使研究生毕业之后， 绝大多数人也只能书面翻译和阅读本学科的外文资料，而不能 流利地与外国专...
【提出问题】(1)在前面做过了“测量小灯泡的电阻”的实验，参考它的思路，怎样测量小灯泡的电功率?(2)如果给你额定电压分别为2.5V和3.8V的小灯泡各一只，你能测出它们的电功率吗?(3)小灯泡上面如果标有额定功率，所标额定功率与通过P=UI测...
查看更多>>