数独程序：https://github.com/wzlk655/Sudoku

　　数独GUI：https://github.com/wzlk655/SudokuGUI

　　2019.12.20 创建，解题思路编写2019.12.27 设计部分编写2020.1.2 性能分析部分编写2020.1.10 测试部分编写，设计部分完善2020.1.15 代码质量分析，GUI部分更新2020.1.16 博客优化，测试部分完善

　　PSP2.1Personal Software Process Stages预估耗时（分钟）实际耗时（分钟）Planning计划2030Estimate估计这个任务需要多少时间205Development开发730900Analysis需求分析3060Design Spec生成设计文档60120Design Review设计复审2020Coding Standard代码规范6030Design具体设计60120Coding具体编码600300Code Review代码复审3030Test测试300480Reporting报告4040Test Report测试报告6020Size Measurement计算工作量1010Postmortem & Process Improvement Plan事后总结, 并提出过程改进计划3030Total总计13002195

　　实现一个命令行程序，程序能：

　　生成不重复的数独终局至文件。读取文件内的数独问题，求解并将结果输出到文件。

　　需求比较明确，所以直接开始建模。

　　数据建模

　　主要的实体就是数独，为了方便数独的生成和变换，将数独分解为9个3x3的子Block，另外，由于详细的需求说明中提到了要求固定生成数独的左上角为某个数字，所以额外给数独一个左上角数字属性。

　　

　　功能建模

　　由于软件本身逻辑并不复杂，功能也较简单，所以只将数据流图分解到1层。

　　

　　1层数据流图区分了具体的指令，生成和求解分别处理。

　　

　　行为建模

　　主要有处理生成请求，处理求解请求和用户参数出错三个状态。

　　

　　数独生成

　　一开始完全没有头绪，于是求助百度，找到了这篇博客，在研究其算法后，发现满足需求，但是想采用更加面向对象的方法进行开发。在参考这篇博客后，阅读相关书籍，发现了如下算法：

　　将9*9的数独划分为9个3*3的方格。使用1-9的排列来按顺序填充一个方格，将方格按照一定顺序变换，可以获得另外8个方格，组成新的数独。通过三行/列一组，组内行/列交换获得更多数独。

　　其中，如何生成数据的排列参考了这篇博客和这篇博客，虽然C++数学库中有类似代码，但是处于数据格式和方便随机生成的考虑自己参考算法实现了排列生成。详见下。

　　思路说明：

　　步骤2中首先生成中间的方格，然后按照如下图对应变换行、列获得其它位置的方格，如图可见生成的结果符合数独要求。周围的小方格都可以由中间的方格交换行列变换而来。

　　

　　步骤3中行列交换是一整行一整列（9个）元素的交换，为了使得交换后的数独仍然是合法的，我们限定交换只发生组内，这样可以证明，交换涉及的行/列和3*3块都仍然是合法的。

　　非严格证明：经过步骤3交换后生成的数独不重复：

　　如果是由同一个步骤2中生成的数独变换而成，则显然被交换的行/列分别和原本不一样，又因为只交换两行/列，所以双方对应行/列也相互区别。如果是由不同步骤2中生成的数独变换而成，显然每次至少有三个（一行/一列）方格不一样，对应的是双方都没有交换的那一组行/列方格。

　　数独求解：

　　暴力搜索–>剪枝—>启发式搜索

　　考虑代码的可理解性和可维护性，参考了这篇博客以及这篇博客中的回溯和DFS思路，决定采用回溯法求数独。将解空间定义为所有解的空格的所有0-9的所有组合。依次尝试每个空格的1-9的所有取值，看能否生成合法的数独，这样算法的复杂度为，n为数独中的空格数目。显然改算式仍然有很大的改进空间，有待后续优化。

　　优化：参考上述博客，在填空进入下一层搜索前，先判断是否是合法数独，如果不合法直接跳过，这样可以有效剪枝。但是需要使得判断数独合法算法能够处理数独不完整时的情况。已经实施。

　　时间原因未尝试实施的优化思路：记录当前行号，尝试数字时快速跳过本行已有的数字；按照数字在空格中出现的比例来顺序尝试，但是需要额外的数据结构和计算比例。

　　由于使用了C++中的面向对象机制，所以尝试了以下使用UML进行建模。但是由于软件本身的功能和之前的系统设计，并不是很方便，所以只画了用例图和类图。

　　UML图

　　用例图

　　识别参与者为玩家和（计算机文件）系统。主要用例为生成数独和求解数独。

　　

　　类图

　　主要为3个类，数独Sudoku，数独的子模块Block和求解数独的工具SudokuSolver，相互关系如下图。

　　

　　详细设计及代码实现

　　由于软件较简单，而且需求分析阶段已经进行了比较明确的建模，所以直接给出部分详细设计并给出部分代码实现。

　　排列生成函数permutation

　　由于生成数独需要首先生成3*3的方格，所以需要对方格的9个位置使用1-9不重复地进行填充。等价于寻找到1个1-9数字的排列。由于需求中要求数独不重复，因此必须有能够生成确定的排列的函数。采用递归思想设wps 的官网的下载入口在哪计函数，流程图如下。

　　

　　源代码及注释如下：

　　Block类主要成员

　　int nums[9]：含有9个元素的数组int seed：用于生成格子内数字的seedBlock(int _seed=1)：根据seed生成排列的构造函数Block(int _seed, int _id)：固定最后一个数，生成其它排列的构造函数void swapColumns(int i, int j)：交换两行的方法void swapRows(int I, int j)：交换两列的方法

　　Sudoku类主要成员

　　Block blocks[9]：9个对应的3*3方格Blockint seed：构建中心Block的seedint id：构建中心Block的idSudoku swapRows(int x, int i, int j)：交换行的方法Sudoku swapColumns(int y, int i, int j)：交换列方法Sudoku changeState(int* seed)：根据一个6个元素的数组做行列变换生成新的数独的方法

　　源代码及注释如下，主要是对seed种的6个元素调用permutation生成对应的排列后做行列变换，难点是如何根据排列来变化行、列使达到对应的顺序：

　　流程图如下，但是实现过程中直接枚举seed中元素，没有使用循环，逻辑略有不同：

　　

　　void toFile(FILE *f)：输出到文件相关操作

　　SudokuSolver类的主要成员

　　int sudoku[81]：存储数独内容的数组。int _backtrackSolve(int holder)：输入空格位置的递归求解数独函数。

　　流程图如下：

　　

　　源代码及注释如下，核心是递归调用，进入下一层之前预先判断合法性实现剪枝：

　　bool _isLegal(int pos)：判断数独是否合法的函数。static int _find_next_empty(int *map, int size)：寻找下一个空格的函数。int solve(std::string method = “backtrack”)：求解方法void print()：输出方法

　　main.cpp中的函数

　　若干打印参数错误的函数void handleCreate(string amount)：处理生成数独

　　源代码及注释如下：

　　handleSolve(string filename)：处理求解数独

　　源代码及注释如下：

　　创建测试项目

　　使用Visual Studio自带的测试项目模板，关联Sudoku项目进行测试。

　　

　　单元测试设计

　　由于Visual Studio Community版本没有覆盖率查看功能，因此只能采用人工方式分析覆盖率。经验证，所有测试用例设计都满足判定/条件覆盖，覆盖率为100%。

　　permutation

　　该函数根据种子seed生成对应的1-9的排列，种子范围为1-9!。函数涉及递归，采用黑盒白盒思想均可，由于实现覆盖较容易，因此设计seed取值最大，最小，最大值偏小，最小值偏大，中间等多个测试用例，全部通过。

　　

　　Block

　　需要测试block直接根据种子生成以及通过指定id（为了实现数独左上角数字固定）情况下能否获得需要的block，另外需要测试swapRaw和swapColumn能否对行列进行所需交换。主要检查block中包含的九元素数组。经过测试符合要求。以下是部分测试设计。

　　编号内容成功1seed=1,3,5643,…生成成功2seed=1,46,3 id=1…9生成成功3交换0，1行成功4交换0，1列成功

　　Sudoku

　　需要测试能否创建和固定左上角创建所需数独，另外需要测试行列交换以及利用行列交换变异生成新数独功能是否正常。经过测试符合要求。以下是部分测试设计。

　　wps office免费版的下载的地方编号内容成功1seed=1,4,63 id=1…9生成成功2交换12行,34行…成功3交换12列,34列…成功4改变状态，seed=000000,000001…成功

　　SudokuSolver

　　需要测试求解出的数独结果是否合法，以及求解时间是否合适等。经测试符合要求。以下是部分测试设计。

　　编号内容成功1装入手动设计的各种数独查看对象是否正常成功2装入各种数独测试判断数独合法的函数成功3测试递归求解的函数处理过程和返回值是否正确成功4人为设置空格测试寻找空格的函数是否正确成功5生成数独题目测试求解结果是否正确成功6求解数独测试打印是否显示正确成功

　　单元测试结果
最新的官网wps的下载网址在哪里
　　主要按照类型设计各种测试Method，尝试各种输入，尝试结果最终版程序未发现问题。但开发过程中测试对发现问题起到了重大帮助。一部分测试由于Visual Studio技术问题无法通过代码反映，但大部分都已经反映在2020.1.16的commit中。

　　

　　进一步测试

　　通过命令行执行程序，对得到的结果进行验证。测试程序在各种情况下的执行情况。

　　编号命令行参数结果1-c 1生成正确2-c 100生成正确3-c 1000000生成正确4-c 1000001输出“请输入1-1000000的数字！”5-c 0输出“请输入1-1000000的数字！”6-cc 12输出“输入不合法，请使用 ‘suodoku.exe -c 数字’ 或 ‘sudoku.exe -s 文件名’ 格式输入。”7-c x输出“请检查-c参数是否为数字。”8-s sudoku.txt正确求解9-s illegalsudoku.txt输出“该数独无法求解！”10-s unexistfile.txt输出“请检查-s参数文件是否存在。”

　　另外比较关键的是验证生成数独的不重复和求解数独的正确性。

　　测试不重复性的代码（Python脚本）：

　　生成个数预期输出实际输出111202020100100100100010001000100000010000001000000

　　测试求解准确性的代码参考GUI中的验证。

　　编号预期输出实际输出1正确结果正确结果2正确结果正确结果3正确结果正确结果4正确结果正确结果5正确结果正确结果

　　创建

　　使用VisualStudio自带的性能分析分析C++代码的执行情况。由于初次版本下发现创建1000个数独就花费了2秒以上，这样生成1000000个数独就需要半个小时以上的时间，感觉有些慢，所以针对创建1000个数独的情况进行了性能分析。结果如下图。

　　

　　

　　

　　

　　可以发现IO操作和生成操作几乎一样费时。每次生成数独都进行了文件读写情况下，读写几乎占用了CPU2/3的性能，而其中两个文件相关函数（appendLine，toFile）中最费时间的是文件的打开关闭，以toFile函数为例，其中文件的打开关闭就占了绝大部分的CPU使用。因此对读写逻辑进行优化，直接接收已经打开的文件，避免频繁操作。经过改进后不再频繁打开文件，结果可见文件操作占用时间大大减少，性能显著提升，10000个数独只占用5秒，符合之前IO操作约占2/3时间的分析，突破了性能瓶颈。

　　

　　

　　这次改进反映在2020年1月2号的commit中。

　　求解数独

　　人为创建了432个数独题目，每个挖去30个空，运行了5秒以上。性能分析如下。

　　

　　可见文件操作（包括标准输入输出）占了大量的时间，去掉printf后，5184个数独在1.7秒完成。性能有较大提升，分析图如下。

　　

　　性能分析总结

　　主要是发现文件相关操作，包括标准输入输出耗费资源都非常大。改进后主要的性能瓶颈是生成数独时的changeState()，或者说是它调用的交换行列swapRows()和swapColumns()；还有暂时保留的求解数独中文件读取fscanf()，的判断数独合法函数isLegal()以及递归函数_backtrackSolve()。由于之前算法设计的时候这些算法已经做了各种优化，所以算法方面暂时没有大动作，从性能分析可以看出，在创建数独的时候更快捷地进行行列交换是目前性能关键，求解数独中一次性读取和改变判断数独的合法性的逻辑可能是之后比较容易的一个性能提升点，目前使用的是控制结构+位操作实现，未来可以尝试用更高效的统一的位操作来改进。

　　尝试使用微软的CppCoreCheck工具进行代码质量分析。

　　暂时有6个警告需要消除。

　　

　　消除警告后生成。

　　

　　

　　项目结构和思路

　　按照要求将UI界面和之前的生成求解器独立为两个项目。方便起见，UI界面采用Python编写，使用tkinter库开发。为了避免Python调用C++的繁琐工作，将之前C++项目得到的.exe文件放在该项目目录下作为依赖，使用文件相互通讯，大大简化了编码工作。其中思路部分参考了这篇博客，但是代码由我个人独立完成最新的官方的wps下载入口在哪呢。

　　面向对象分析设计

　　用例图

　　

　　类图

　　只有两个类，ChooseNumber对象中生成SudokuGUI的一个对象。

　　

　　状态图

　　由于系统比较简单，这里直接给出了整个系统的状态图。

　　

　　设计说明

　　首先创建输入数独数量的界面，然后根据用户输入判断合法性后再生成实际的数独界面。通过system调用Sudoku.exe文件执行-c创建任意数量数独，GUI程序读取生成文件，依次显示加载到界面上。注：详细了解需求后，SudokuGUI类中维护了所有数独的列表。将Entry和SudokuGUI类的内部列表相关联，用于显示数独题目和获取用户解答。将读取的数独进行挖空，按照每个3x3至少两个，总体不少于30个不多于60个的约束随机挖空，通过9x9个Entry控件显示数独界面，将没有挖空的Entry设置为只读。加入检查机制，如果用户输入非法，未输入，结果错误等都有相应的提示。如果用户解答正确，也有相应的说明。

　　界面设计

　　输入数字界面

　　

　　功能比较直观

　　数独界面

　　

　　整体使用Pack来组织，数独部分采用Grid来构造界面。最上方为当前题号，用户在上方的9x9方格的空格中填写数字，点击提交则程序对结果进行检验，点击下一个则进入一个新的题目，点击上一个则返回上一题，之前填写的会被保留。

　　实现（部分核心函数）

　　数独界面初始化相关核心代码如下：

　　验证数独解答的函数代码如下

　　

　　该程序首先检查所有输入是否都是1-9的整数，如果不是则给出相应的提示，通过检查后，就可以直接通过枚举每行每列没格3*3小方格中是否出现了9种数来判断数独是否合法了。

　　测试

　　由于程序本身的代码结构比较简单，主要是GUI界面的测试，因此直接进行系统测试。对应结果如下。

　　编号操作预期反馈实际反馈通过1生成个数为1进入数独界面进入数独界面通过2生成个数为1000000弹出错误提示框弹出错误提示框通过3生成个数为0弹出错误提示框弹出错误提示框通过4生成个数为1000001弹出错误提示框弹出错误提示框通过5页间跳转成功跳转成功跳转通过6部分解答来回跳转保留输入保留输入通过7正确解答提交弹窗提示回答正确弹窗提示回答正确通过8非法字符提交弹窗提示非法字符弹窗提示非法字符通过9空白格解答提交弹窗提示空白弹窗提示回答空白通过10数字超范围解答提交弹窗提示超范围弹窗提示超范围通过11错误解答提交弹窗提示回答错误弹窗提示回答错误通过

　　结果演示

　　生成并显示数独

　　见上图界面设计。

　　解答输入结果

　　由于为了实现生成任意数量数独，最终界面有更改，此处是最初版本的界面

　　

　　验证结果

　　空值或非法输入。此处后方是最初版本的界面。

　　

　　特别地，如果不是1-9范围内的数字。此处后方是最初版本的界面。

　　

　　如果解答有问题（结果不满足数独条件）。此处后方是最初版本的界面。

　　如果回答正确。此处后方是最初版本的界面。