软件工程个人项目总结-数独
Github项目地址
??链接
包含博客
??这篇博客将之前的每周所发整合成了一篇
PSP表格
| PSP2.1 | Personal Software Process Stages | 预估耗时（分钟） | 实际耗时（分钟） |
|---|---|---|---|
| Planning | 计划 | 60 | 60 |
| · Estimate | · 估计这个任务需要多少时间 | 60 | 60 |
| Development | 开发 | 870 | 1710 |
| · Analysis | · 需求分析 (包括学习新技术) | 120 | 120 |
| · Design Spec | · 生成设计文档 | 120 | 160 |
| · Design Review | · 设计复审 (和同事审核设计文档) | 60 | 30 |
| · Coding Standard | · 代码规范 (为目前的开发制定合适的规范) | 120 | 60 |
| · Design | · 具体设计 | 60 | 120 |
| · Coding | · 具体编码 | 240 | 500 |
| · Code Review | · 代码复审 | 30 | 120 |
| · Test | · 测试（自我测试，修改代码，提交修改） | 120 | 600 |
| Reporting | 报告 | 150 | 240 |
| · Test Report | · 测试报告 | 60 | 120 |
| · Size Measurement | · 计算工作量 | 30 | 30 |
| · Postmortem & Process Improvement Plan | · 事后总结, 并提出过程改进计划 | 60 | 90 |
| 合计 | 1080 | 2010 |
需求分析
需求
运行一个命令行程序，程序能：
?1. 生成不重复的数独终局至文件。
?2. 读取文件内的数独问题，求解并将结果输出到文件。
数据建模
将数独分成9个宫进行求解，ER表示如下，因为数独左上角第一块确定，所以将其看作数独的属性。
功能建模
数据源：用户
数据终点：文件
主要数据流：生成指令、求解指令、数独（待求解），以及终局
主要支持文件：待求解数独文件
主要处理过程：生成终局、求解数独
0层图
??对系统进行求精，划分系统的子系统。
行为建模
解题思路
??在最开始拿到题目的时候，想起上学期算法课程学过的回溯算法，决定用会回溯算法进行实现，所以翻看了算法设计的课本和ppt，对回溯算法重新进行了学习。在生成n个不同局面和求解给定数独的思路大致一致，但有在细节处的处理有些不同。首先是生成n个不同的局面，按行进行循环，有一个二维数组保存每个位置的可能数字，从可能数字中随机选一个放在该位置，若该位置找不到可能的位置，则回到上一个，修改上一个位置的解。不断进行回溯，直到所有的位置都合法。若是对给定局面进行求解，则将空白位置用数组记录下来，只对空白位置进行回溯即可。
??但在该回溯算法中，搜索时盲目的，效率较低，最差的实现对每个空方格试探所有可能的数字，有大量的时间浪费。并且如果需要生成多个终局时，每一个终局都是通过回溯实现，且生成不同的终局由Random()进行数字选择实现，但实际上Random生成伪随机数，在一定时间会生成相同随机数，无法保证在生成终局数目足够大时，不会产生两个相同的终局。
??因为算法效率有很大的改进空间，以及无法保证在n足够大时，所有终局都相异，所以在对代码重构的过程中，引入了排列组合的算法，对原有进行优化。将数独分成9个3X3的小方块，每个小方块是一个宫。
??参考维基百科提供的一个生成终局思路，由第一宫生成其余八个宫。对第一宫中的块进行排列组合即可，因为生成终局时，要求左上角的第一个数为：（学号后两位相加）%9+1，(1+3)%9+1=5，所以左上角为5，且不允许改变。即在第一宫内只有八个块可以移动，有8!=40320种情况，并且在每一宫内（除了第一宫）进行列列变换有3!×3!×3!×3!=1296，第二宫和第三宫可以交换，第四宫和第七宫可以交换有2!×2!=4，总共可以生成209,018,880个终局(大于1,000,000)，此方案可行。
??对于各种全排列，使用递归的方式实现。
设计实现过程
???编译器：Intellij IDEA 2019.2
???语言：java
???运行环境：JDK 1.8
活动图
顺序图
??下面是生成终局的顺序图
??下面是求解数独的顺序图
类图
???共有三个类，Main用于判断输入是否合法、将终局写入文件、判断输入命令是否合法，Generate类用于生成终局，Solve类用于求解数独。
具体代码说明
Generate中主要函数：
???generateSudoku 外部调用的接口，传入一个n(n<=1,000,000)，即可以生成n个终局。
??createSeed 将第一宫作为种子，进行交换操作，得到不同的种子。
??createMap 通过种子的变换，得到该种子生成的第一个终局。
??changeIndex 对于第一个终局进行行列变换，生成不同的终局。
??writeToOutput 将生成的int[ ] [ ]的终局，按照输出格式要求，存放在一个char[]中 。
changeIndex流程图如下
??具体实现代码如下所示，在goalNum=1时，不用进行变换，在>1开始，先交换index[16]和index[17]，即先在第三大列内进行列变换，可以有6中不同的终局，接着在第二大列内进行交换，依次类推，到行进行交换，可以快速产生大量不相同的终局。
/**
* @Title: changeIndex
* @Description: 对宫内的行列进行全排列
* @param a
* @param start
* @param end
* @return void
* @throws
*/
public void changeIndex( int start, int end) {
int i;
//分段进行全排列
if (start == end) {
if (end == 5) {
changeIndex( 6, 8);
}else if(end==8){
changeIndex( 12, 14);
}else if(end==14){
changeIndex( 15, 17);
}
else {
writeToOutput();
}
}
else {
for (i = start; i <= end; i++) {
swap(index, start, i);
changeIndex( start + 1, end);
if (nowNum == goalNum) break;
swap(index, start, i);
}
}
}
Solve中主要函数
??findSolution外部调用的接口，传入一个txt的绝对路径，即可对该txt中的数独进行求解。
??dealFile将txt中的所有数独，存在一个int[]中，并得到要求解的数独数目。
??initCriterion将Criterion(表示行列宫没有用过的数)初始化，并将数独中出现过的数在Criterion进行标记。
??chooseCriterion递归对数独进行求解。
chooseCriterion流程图
??chooseCriteron和dealWithCriterion是求解数独的主要两个函数。chooseCriterion中state表示当前是否能找到可行解，找到返回true，没找返回false。先循环1-9九个数，找到一个所在行、列、宫都没有使用过的数放入，然后调用dealWithCriterion函数，若后面的位置没有待求解位置，则返回true，此时state为true，结束求解。若后面仍有待求解位置(a,b)，则dealWithCriterion函数返回chooseCriterion(a, b)进行求解，若可以找到可行解，则前面所求解保留，若找不到，则修改前面找到的可行解。本质是利用回溯算法进行求解。
??起初两个函数写在一起，但在代码质量检查时，该函数复杂度太高，所以拆分成两个函数
/**
* @Title: chooseCriterion
* @Description: 回溯选择合适的数
* @param row
* @param col
* @return boolean
* @throws
*/
private boolean chooseCriterion(int row, int col) {
int value;
boolean state = false;
for (int k = 0; k < 9; k++) {
if(!state) {
value = k + 1;
if (!fill(row, col, value)) {
continue;
}
map[row][col] = value;
usedNum(row, col, value);
state = dealWithCriterion(row, col);
if (!state) {
releaseNum(row, col, value);
map[row][col] = 0;
}
}
}
return state;
}
/**
* @Title: dealWithCriterion
* @Description: 查找是否有空位要求解
* @param row
* @param col
* @return boolean
* @throws
*/
public boolean dealWithCriterion( int row, int col) {
//没有空位
boolean state = false;
for (; row < 9; row++) {
for (; col < 9; col++) {
if (map[row][col] == 0) {
state = true;
break;
}
}
if (state)
break;
col = 0;
}
//没有空位
if (!state) {
return true;
}
return chooseCriterion(row, col);
}
Main中主要函数
?stringToFile传入一个char[]，将其写入可执行文件同级文件夹中的layout.txt(没有会创建)。
?isNumeric，whetherSolve，whetherGenerate都是判断输入是否合法。
测试
? 使用Junit5对三个类分别进行单元测试，单元测试的编写思路是黑盒测试，运用了路径覆盖和边界覆盖。对接口功能、边界条件等进行测试，并使测试覆盖率尽可能，测试用例尽可能全面。
? MainTest用于测试输入是否合法，以及是否可以顺利写入文件，
? GenerateTest测试其中的函数是否正常，并进行了重复性检测，检测器生成的1000个终局中是否有相同的情况。
? SolveTest对Solve中部分主要函数进行了检测，并对求解结果进行了有效性检测，判断是否是否求出了正确的数独解。
? 单元测试覆盖率
Main部分测试设计（期待状态=实际状态，即为成功）
| 编号 | 内容 | 状态 |
|---|---|---|
| 1 | args[0]=11，args[1]=null | 成功 |
| 2 | args[0]="-c", args[1]="0" | 成功 |
| 3 | args[0]="-c", args[1]="1_000_001" | 成功 |
| 4 | args[0]="-c", args[1]="1_000_000" | 成功 |
| 5 | args[0]="-c", args[1]="D:/1.txt" | 成功 |
| 6 | args[0]="-s", args[1]="D:/1.txt" | 成功 |
| 7 | args[0]="-s", args[1]="D:/app/" | 成功 |
Generate部分测试用例
| 函数 | 内容 | 状态 |
|---|---|---|
| createSeed | seed={1,2,...9}，goalNum=1 | 成功 |
| createSeed | seed={1,2,...9}，goalNum=100 | 成功 |
| createMap | int[][] temp={{5,1,2,7,8....}，goal=1 | 成功 |
| createMap | int[][] temp={{5,1,2,7,8....}，goal=1 | 成功 |
| swap | 交换两个数 | 成功 |
| generateSudoku | count=1000(检测生成的1000个终局是否重复) | 成功 |
| generateSudoku | count=1,000,000(检测生成的1,000,000个终局是否重复) | 成功 |
Solve部分测试用例
| 函数 | 内容 | 状态 |
|---|---|---|
| findSolution | PATH=txt路径，里面有1000个数独，检查找到的解是否正确 | 成功 |
| findSolution | PATH=txt路径，里面有100个高难数独，检查找到的解是否正确 | 成功 |
| fill | Criterion[0]=510,Criterion[9]=510,Criterion[18]=510，row=0,col=0,value=5; | 成功 |
| releaseNum | PATH=txt路径,row=0,col=0,value=4; | 成功 |
| getBlock | row=0,col=0 | 成功 |
| getBlock | row=3,col=4 | 成功 |
通过命令行执行程序，对得到结果进程测试
| 编号 | 命令行参数 | 结果 |
|---|---|---|
| 1 | -c 0 | 能生成的终局在1-1,000,000之间 |
| 2 | -c -1 | 能生成的终局在1-1,000,000之间 |
| 3 | -c 1000 | 运行成功 |
| 4 | -c 1000000 | 运行成功 |
| 5 | -c 1000001 | 能生成的终局在1-1,000,000之间 |
| 6 | -c | 生成终局命令为：java sudoku -c 阿拉伯数字 |
| 7 | -a | 您的输入不正确 生成终局命令为：java sudoku -c 阿拉伯数字 求解数独命令为：java sudoku -s puzzle.txt的绝对路径 |
| 8 | -s D:\app\ | 路径需指向一个txt文件 |
| 9 | -s D:\app\unexisted.txt | 系统找不到指定的文件 |
| 10 | -s puzzle.txt | 运行成功 |
代码质量分析
? 用SonarLint插件对每个java文件进行代码质量优化
? 分析过后，除了Main类中因为需要打印命令错误提示，仍存在一些warning，其余文件中的warning全部消除。
性能改进
??用Intellij中插件JProfiler进行程序性能分析
??最初的程序每生成一个终局，直接写入文件，且进行回溯时，多次进行值的交换。为了保证随机性，每一次将所有可能值先放入链表，然后将随机选取一个放入该空位。在求解数独时，先读取一个数独，求解后写入文件，再继续读取下一个数据。这种算法会频繁创建很多对象，且读写会花费大量的时间。
??改进后，时间上有了非常大的提升，且在回溯，用一个27位数组Criterion，前九位表示每一行可能解，中间九位表示每一列可能解，最后九位表示每一个宫的可能解，且每一个数可以表示成一个九位的二进制，从右到左依次表示1-9，若Criterion[0]=000_000_001，则表示第一行只有1没有用过，该位置的可行解只有1。选择一个数时只需将该数与对应的下标的Criterion进行与运算，即可将该数标记为使用，这样减少了反复复制的时间。且改进后不再随机选取可行解，按顺序进行选择。
??并且改进后每生成一个终局，先放在一个char数组中，生成所有的终局，统一写入文件；在求解数独时，一次读取出所有的待求解数独，每个分别求解，再统一写入。
??下图为Jprofiler中提供的CallTree，通过树形图体现了方法间的层次调用关系，并按照执行总时间从小到大排列。
??改进之前，用FileWriter写入文件，生成1000个终局需要12s左右。每生成一个终局马上写入文件。下图看到关闭流花费了大量的时间。
??改进后，用BufferedWrite写入文件，由于含有缓冲区，所以效率要比FileWriter高，但内部仍用FileWrite进行读写。在生成1000个终局时，总耗时为0.034s。由下表写入文件所消耗的时间远大于生成终局。
??以后讨论情况均为改进以后
??在生成1,000,000个终局时，总耗时0.805。stringToFile，即将终局写入文件所占比例最大，即耗时最长，但生成终局的方法generateSudoku执行耗时虽然不是最长，但仍占有较大的比例。
??综合生成1000和1,000,000个终局可得，在生成终局的情况下，stringToFile时消耗最多的函数。
??在求解数独时，首先读取1000个数独，进行求解，总耗时0.325s。此时findSolution函数耗时最多，但在这个函数中会调用其他函数，其中dealFile即读取文件耗时最多。
??求解10,000个数独时，findSolution耗时最多，在该函数调用的函数中，SolveSudoku求解数独的函数耗时超过了读取文件的耗时。在求解数目较小，读取文件的时间相对较长，在求解数独变大以后，求解数独的时间要更长。
GUI界面开发
开发运行环境
??运行环境：JDK1.8
??运行命令：java -jar sudokuGUI.jar
??语言：java
??开发环境：Intellij IDEA 2019.2，JavaFX Scene Builder 8.3.0
项目结构和说明
??为了利用之前的源代码，UI界面采用javafx进行开发，使用MVC框架来设计整个应用，使用了数据绑定，通过构建容器组件，添加menu、监听器等实现图形化界面功能。
软件功能说明
??主要页面如下所示，一打开应用自动进行计时。
??点击菜单中的开始，可以开始新游戏、提交当前页面，查看答案，退出游戏。
??点击提交时，计时器停止，若有空位置没有填，会提示填满再提交，若有错误会弹窗会提示，完全正确时会弹窗恭喜用户。
面向对象分析设计
用例图
类图
总共有五个类
Main用于显示UI界面，界面用xml编写，在sample.xml中。
Controller监听图形页面、鼠标、键盘等。
Solve验证用户提交的数独是否正确。
Generate用于生成终局，对终局随机挖空，形成数独，显示在UI中。
AlterInfo用于弹窗提示。
SudokuCell表示数独中的每一个小块，控制是否可以输入，显示数字等。
状态图
设计思路
??GUI中的主体代码和命令行部分几乎一致，最开始选择生成数独的回溯算法。最初实现UI界面，用了优化以后利用排列组合快速生成终局的算法，但因为终局是由变换第一宫形成的，所以存在规律性，降低数独的可玩性。所以采用了最初生成终局的回溯算法。
??实现思路是先通过回溯算法生成一个终局，因为要求最少挖30个空，最多挖60个空，每个宫中最少有两个。当每个最少挖4个，4×9=36符合要求，每个宫最多挖6个，6×9=54个符合要求。所以循环九个宫，每个宫产生一个随机数n(4<=n<=6)，然后在1-9中生成n个不同的随机数，在该宫中将n个随机数所在的位置挖掉，便生成了一个数独。
??在编写代码的过程中，卡壳了很久一直在思考如何保证数独解的唯一性，但因为自己对这部分算法的理解并不是很深入，所以放弃了保证了数独解的唯一性。用户提交数独时，不与最初生成的终局比较，而是利用循环检查用户提交的答案中是否有错误，没有错误即为正确答案。若用户选择查看答案，则提供最初的终局。
??自定义了一个数据类型SudokuCell，来存放数独中的每一个小块，其中设置一个属性write保证可以多次修改答案，若数独中该位置需要填写，则将write设置为true，若不需要则设置为false，并且可以对每一个SudokuCelle用css进行美化，使数独的外观更加美观。
具体代码实现
??对用户提交数独进行检查，正确时返回true，错误时返回false，这个方法在命令行中用于测试，检查对txt数独中求解时，是否有错误。
/**
* @Title: checkSolution
* @Description: 检查结果
* @param data
* @return boolean
* @throws
*/
boolean checkSolution(int[] data)
{
int index=0;
int[] criterion=new int[27];
Solve s=new Solve();
for (int j = 0; j < 27; j++) {
criterion[j] = 511;
}
s.setCriterion(criterion);
if(!checkSudoku(data,index,s))
return false;
return true;
}
/**
* @Title: checkSudoku
* @Description: 检查数独答案是否正确
* @param data
* @param index
* @param s
* @return boolean
* @throws
*/
private boolean checkSudoku(int[] data,int index,Solve s) {
for (int j = 0; j < 9; j++) {
for (int k = 0; k < 9; k++) {
while (data[index]>9 || data[index]<1)
{
index++;
}
int temp = data[index++];
if (!s.fill(j, k, temp)) {
Logger logger=Logger.getLogger("SolveTest");
logger.setLevel(Level.SEVERE);
String msg="row:"+(j+1)+"clo:"+(k+1)+"value:"+temp;
logger.severe(msg);
return false;
}else{
s.usedNum(j,k,temp);
}
}
}
return true;
}
测试
??因为GUI项目中，除了UI部分代码，都是在命令行中经过测试的代码，所以只进行简单的系统测试，检测页面的响应、监听等是否正常。
| 编号 | 操作 | 预期结果 | 实际结果 | 状态 |
|---|---|---|---|---|
| 1 | 页面有空位，点击提交 | 未完成弹窗 | 未完成弹窗 | 通过 |
| 2 | 页面没有空位，存在错误，点击提交 | 错误弹窗 | 错误弹窗 | 通过 |
| 3 | 正确完成数独，点击提交 | 正确弹窗 计时停止 |
正确弹窗 计时停止 |
通过 |
| 4 | 点击查看答案 | 显示答案 计时停止 |
显示答案 计时停止 |
通过 |
| 5 | 点击退出 | 退出程序 | 退出程序 | 通过 |
| 6 | 点击新游戏 | 开始新游戏 | 开始新游戏 | 通过 |
| 7 | 在空位输入非数字字符 | 输不进去 | 输不进去 | 通过 |
| 8 | 在空位输入数字字符 | 空位显示该数字 | 空位显示该数字 | 通过 |
| 9 | 点击查看答案以后，点击提交 | 正确弹窗 | 正确弹窗 | 通过 |
| 10 | 点击关于 | 信息弹窗 | 信息弹窗 | 通过 |
| 11 | 点击帮助 | 帮助弹窗 | 帮助弹窗 | 通过 |
简要开发过程
| 时间 | 内容 |
|---|---|
| 2019年12月19日 - 2019年12月20日 | 需求分析、概要设计 |
| 2019年12月26日 - 2020年1月1日 | 基本完成命令行功能 |
| 2019年12月26日 - 2020年1月1日 | 开始单元测试 |
| 2020年1月2日 - 2020年1月3日 | 修改算法、对代码结构进行优化，完成测试 |
| 2020年1月4日 - 2020年1月16日 | 代码质量检测、UI编写 |
| 2020年1月17日 - 2020年1月18日 | 博客优化 |