数独实验报告范文

  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让我不断思考,改进了最初的算法。编程是确实是一个克服困难、不断改进与超越的过程。总有新的数据摆在面前,把原来的算法打击得很惨,激励着我们研究更加先进的算法。

原创文章,作者:fanwen,如若转载,请注明出处:https://fanwen.hongwu.com/21168.html

(0)
上一篇 2022年8月5日 下午3:13
下一篇 2022年8月5日 下午3:15

相关推荐

  • 关于《人体组织解剖学》课程实验报告的格式

      实验报告本封面课程名称:《人体组织解剖学》。   每次实验报告的格式:   实验题目:实验二 骨骼和骨骼肌的大体解剖结构观察。   实验日期:201X年3月12日。   一、实…

    实验报告 2022年8月18日
  • 构建学校德育管理与评价体系的实验报告

      一、问题的提出    (一)在第三次全国教育工作会议上的讲话中指出:“要说素质,思想政治素质是最重要的素质”。可见德育是素质教育的核心,研究和构建学校德育评价体系,是…

    实验报告 2022年9月20日
  • 半导体工艺化学实验报告

      实验名称:硅片的清洗   实验目的:1.熟悉清洗设备   2.掌握清洗流程以及清洗前预准备   实验设备:1.半导体兆声清洗机(SFQ-1006T)   2.SC-1;SC-2…

    实验报告 2023年8月26日
  • 关于初中生物的实验报告范文

      实验: 练 习 使 用 显 微 镜   目的要求:   1、练习使用显微镜,学会规范的操作方法。   2、能够独立操作显微镜。   3、能够将标本移动到视野中央,并看到清晰的图…

    实验报告 2022年11月5日
  • 关于路抢答器的实验报告

      指导老师:陈老师   成员(第四组):章海洋 肖悦 何细义   一、设计题目:   八路抢答器的设计   二、设计要求:   1.设计一个智力竞赛抢答器,可同时供8名选手或者8…

    实验报告 2022年12月7日
  • “小学教师心理素质优化研究”实验总结

      “小学教师心理素质优化研究”在我们实验点开展五年了。这个课题的实验,适应教育改革发展、全面推进素质教育的需要,在我们学区收到了比预期更好的成效,有力地促进了广大教师心理素质的提…

    实验报告 2022年11月13日
  • 筛板精馏塔精馏实验报告范文

      筛板精馏塔精馏实验   6.1实验目的   1.了解板式塔的结构及精馏流程   2.理论联系实际,掌握精馏塔的操作   3.掌握精馏塔全塔效率的测定方法。   6.2实验内容 …

    实验报告 2022年10月17日
  • 会计实务实验报告范文

      一、实验目的:   众所周知,经济越发展,会计越重要。是的,会计是一门理论性和实践性结合紧密的学科。对于一名即将毕业走上工作岗位的大学生来说,学好会计学的相关理论知识,并强化对…

    实验报告 2022年11月1日
  • 初中化学实验报告总单

      1.常用仪器的名称、形状和主要用途。   2.化学实验的基本操作   (1)药品的取用和称量   (2)给物质加热   (3)溶解、过滤、蒸发等基本操作   (4)仪器连接及装…

    实验报告 2022年8月23日
  • 大学物理实验报告

      物理学习想必少不了实验证明吧,那么,下面是第一范文网小编给大家整理收集的大学物理实验报告,供大家阅读参考。 大学物理实验报告1   实验目的:通过演示来了解弧光放电的原理   …

    实验报告 2022年10月9日

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注