安卓数独实验报告

1 / 6 安卓数独实验报告 ? 河南科技学院 物联网移动应用开发课程设计报告 设 计 题 目：基于 android 的数独游戏设计 班 级：学 号： 2016156555 姓 名： 胡 建 刚 指 导 教 师： 许 睿成 绩： 信 息 工 程 学 院 课程设计报告说明 一、写报告前，请认真阅读课程设计报告说明。 二、打印装订要求 1、一律用 A4 纸，双面打印，并左侧装订。报告正文部分均采用宋体小四 。课程设计报告说明页也打印。 2、课程设计概述部分占一页；课程设计内容长度根据实际需要填写；结论和指导教师评语及成绩单独占一页。保证打印格式工整。 3、指导教师评语及成绩部分由指导教师填写。 三、报告内容要求 1、课程设计目的结合实际自己写，不要雷同。 2、课程设计原理简要说明所完成课程设计项目所涉及的理论知识。 3、课程设计内容 这是课程设计报告极其重要的内2 / 6 容。概括整个课程设计过程。 毕业设计开题报告 2016 年 12 月 21 日 开题报告填写要求 1开题报告作为毕业设计答辩委 员会对学生答辩资格审查的依据材料之一。此报告应在指导教师指导下，由学生在毕业设计工作前期内完成，经指导教师签署意见及所在专业审查后生效； 2开题报告内容必须用黑墨水笔工整书写或按教务处统一设 计的电子文档标准格式打印，禁止打印在其它纸上后剪贴，完成后应及时交给指导教师签署意见； 3“文献综述”应按论文的格式成文，并直接书写 在本开题报告第 一栏目内，学生写文献综述的参考文献应不少于 15篇； 4有关年月日等日期的填写，应当按照国标 GB/T 7408 94 数据元和交换格式、信息交换、日期和时间表示法规定的要求，一律用阿拉伯数字书写。如“ XX 年 4 月26日”或“ XX-04-26”。 毕 业 设 计开 题 报 告 Project2： Sudoku 实验报告 3 / 6 一、 算法描述 求解 Sudoku让人最容易想到的方法是穷举每个方格可能的值，如果符合条件，则得到解，不符合条件则进行回溯 。通过递归的方法，显然可以得到数独的解。 我想到的简单的递归方法，是每一行从左到右，试验每一个方格可能的数字，进行递归。这种方法看似非常麻烦，实际上对于一般的数独题，速度是非常快的，思想比较简单，写出来的代码也非常简单、易懂。 算法 1：简单递归方法 从第一个格开始，从 1 到 9 试验，是否满足行、列、九宫格互不相同的条件。若满足条件，则填入该数字，再试验下一个格。当一个格子出现没有数字能填的情况时，说明已经填的数字有误，回溯，再进行递归。 算法 2：优化的递归算法 先遍历所有格子，统计每种格子可能出现数字的个数。每次挑选可能出现数字个数最少的格子来进行递归。 设置三维数组 possijk来存储可能出现数字的信息。 possij0记录 i 行 j 列的格子可能出现数字的个数， possijk 若 possijk=1，表示 k 可能在格出现。若 possijk=0，表示 k不可能在格中出现。每次找 possij0最小的格子，来进行下一个递归。 算法 3：生成数独棋盘的算法 4 / 6 我最开始的想法是穷举法，随机生成满足行各不相同的 9行，再判断 9 宫格、每列是否符合要求，符合条件时，随机生成停止。然而，这种算法的当然时间复杂度显然是过高。第 99 一步的随机生成的次数是 9*9/P9=9608。随机生成一组棋盘耗时就非常大。 后来，我从求解的个数的程序获得启发。算法二对于 1000 多组解的数独棋盘，解起来也很快。随机生成填 9个方格，再用算法一的方法解出来，取第一组正确的解作为棋盘即可生成填好的棋盘。再把一定数量的格子的数字随机删除，计算解的个数。如果解唯一， 就得到了棋盘。 二、 数据结构 这两种算法的数据结构不是非常复杂，只是普通的数组。 算法一：数组 aij 算法二：数组 aij和 possijk 算法三：数组 aij和 possijk 三、 时间效率分析 算法 1：这种算法在 tsinsen 系统上只用了 15ms 得到全部答案。 虽然这种算法在 tsinsen 系统的测试中有很好的表5 / 6 现，但是我试了试在几道骨灰级难度的题，发现这种算法可能会用到 10 秒以上的时间，并且测试数据不同，时间差异非常大。 我认为，这种算法的漏洞在于，如果开始的格子可能出现的数字非常多，递归树开始的枝会非常多。并且，我们一般做数独题，都会先挑可能出现数字个数最少的格子来填，充分利用了已知条件。然而，这种算法只按格子的行列顺序来试验，显然非常傻。于是，我想出了第二种算法。 算法 2： 非常令人失望的是，虽然它能在短时间内解出骨灰级题目，但是，和上一个算法相比，对于简单的题目，它比较耗时。在 tsinsen 系统中测试的时间是 91ms。它的缺陷在于，每 次递归都必须更新格子所在的行、列、九宫格所有的元素。每次要求 20 个数的 possij。回溯同样要更新。并且求 possij的函数时间复杂度是 O。每一步所耗时间比上一种算法多很多。但是，总的试验的步数能显著减少。 所以，这种算法适用于数独解题的动画演示和解极难题目。 四、 程序结构 算法一： 算法二： 五、 6 / 6 运行结果 五、总结和反思 后来老师提高了难度，要求程序能求出多解数独题的解的个数。几千个 解的数据都能迅速得出答案，但是几万个解的数据，需要很长时间，更别提几百万的数据。这两种递归的