《数独实验报告范文》由会员分享，可在线阅读，更多相关《数独实验报告范文（2页珍藏版）》请在金锄头文库上搜索。
1、数独实验报告范文 Sudku数独实验报告 一、算法描述 求解Suoku让人最容易想到的方法是穷举每个方格可能的值，如果符合条件,则得到解，不符合条件则进行回溯。通过递归的方法,显然可以得到数独的解。 我想到的简单的递归方法,是每一行从左到右,试验每一个方格可能的数字,进行递归。这种方法看似非常麻烦，实际上对于一般的数独题，速度是非常快的，思想比较简单，写出来的代码也非常简单、易懂。 算法1:简单递归方法 从第一个格开始,从1到试验,是否满足行、列、九宫格互不相同的条件。若满足条件，则填入该数字，再试验下一个格。当一个格子出现没有数字能填的情况时,说明已经填的数字有误,回溯，再进行递归。 算法:
2、优化的递归算法 先遍历所有格子,统计每种格子可能出现数字的个数。每次挑选可能出现数字个数最少的格子来进行递归。 设置三维数组p来存储可能出现数字的信息。ossij0记录行j列的格子可能出现数字的个数，sijk（1算法：生成数独棋盘的算法我最开始的想法是穷举法,随机生成满足行各不相同的行,再判断宫格、每列是否符合要求，符合条件时,随机生成停止。然而,这种算法的当然时间复杂度显然是过高。第99一步的随机生成的次数是9*9/960。随机生成一组棋盘耗时就非常大。后来，我从求解的个数的程序获得启发。算法二对于1000多组解的数独棋盘,解起来也很快。随机生成填9个方格,再用算法一的方法解出来,取第一组正
3、确的解作为棋盘即可生成填好的棋盘。再把一定数量的格子的数字随机删除，计算解的个数。如果解唯一，就得到了棋盘。 二、数据结构 这三种算法的数据结构不是非常复杂,只是普通的数组。 算法一:数组a 算法二:数组ij和sj 算法三：数组ij和possij 三、时间效率分析 算法:这种算法在se系统上只用了5ms得到全部答案。 虽然这种算法在tsis系统的测试中有很好的表现,但是我试了试在几道骨灰级难度的题,发现这种算法可能会用到10秒以上的时间,并且测试数据不同，时间差异非常大。 我认为,这种算法的漏洞在于，如果开始的格子可能出现的数字非常多，递归树开始的枝会非常多。并且,我们一般做数独题，都会先挑可
4、能出现数字个数最少的格子来填,充分利用了已知条件。然而,这种算法只按格子的行列顺序来试验，显然非常傻。于是,我想出了第二种算法。 算法2：这种算法耗时长。 非常令人失望的是,虽然它能在短时间内解出骨灰级题目,但是,和上一个算法相比,对于简单的题目，它比较耗时。在tsnsn系统中测试的时间是9s。它的缺陷在于,每次递归都必须更新(i，)格子所在的行、列、九宫格所有的元素。每次要求20个数的ossij。回溯同样要更新。并且求posij的函数时间复杂度是（）。每一步所耗时间比上一种算法多很多。但是,总的试验的步数能显著减少。 所以,这种算法适用于数独解题的动画演示和解极难题目。四、程序结构 五、运行结果 六、总结和反思 后来老师提高了难度,要求程序能求出多解数独题的解的个数。几千个解的数据都能迅速得出答案,但是几万个解的数据,需要很长时间，更别提几百万的数据。这两种递归的算法都有问题，优化的空间也有限,需要更强大、高效的算法。这次Projet让我不断思考，改进了最初的算法。编程是确实是一个克服困难、不断改进与超越的过程。总有新的数据摆在面前,把原来的算法打击得很惨,激励着我们研究更加先进的算法。
