2019年数独实验报告范文

20192019年数独实验报告范文年数独实验报告范文 92019年数独实验报告范文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让我不断思