SudokuProject
- 1）
- 2）在开始实现程序之前，在下述PSP表格记录下你估计将在程序的各个模块的开发上耗费的时间。
| PSP2.1 | Personal Software Process Stages | 预估耗时（分钟） |
|---|---|---|
| Planning | 计划 | 30 |
| · Estimate | · 估计这个任务需要多少时间 | 30 |
| Development | 开发 | 365 |
| · Analysis | · 需求分析 (包括学习新技术) | 30 |
| · Design Spec | · 生成设计文档 | 30 |
| · Design Review | · 设计复审 (和同事审核设计文档) | 20 |
| · Coding Standard | · 代码规范 (为目前的开发制定合适的规范) | 25 |
| · Design | · 具体设计 | 25 |
| · Coding | · 具体编码 | 200 |
| · Code Review | · 代码复审 | 20 |
| · Test | · 测试（自我测试，修改代码，提交修改） | 15 |
| Reporting | 报告 | 60 |
| · Test Report | · 测试报告 | 15 |
| · Size Measurement | · 计算工作量 | 15 |
| · Postmortem & Process Improvement Plan | · 事后总结, 并提出过程改进计划 | 30 |
| 合计 | 455 |
- 3）解题思路描述。即刚开始拿到题目后，如何思考，如何找资料的心路历程。
- 首先想到的是递归，遍历，这种方法可以找到全部解，但是需要花费大量时间来计算。
- 之后呢想到了变换，通过一个随机数组，位移变换来产生一个数独，这种方式时间复杂度低，快速，但是不能找到全部解。算了一下，能找到362880个解，这个数值也算可以了，就采用的这种方法。 查找资料主要是通过在网上查阅，看博客，看哪种方式更好，更贴合实际需求。- 4）设计实现过程。设计包括代码如何组织，比如会有几个类，几个函数，他们之间关系如何，关键函数是否需要画出流程图？
本程序主要有以下4个函数：主函数(main)/随机数组函数(my_rank)/数独构建函数(build)/写入文件函数(arr_write)
各个函数关系如下图所示：
程序的流程图具体如下：
- 5）代码说明。展示出项目关键代码，并解释思路与注释说明。
- 这是一维数组的遍历程序，通过递归来实现的，１-9自由排列
void my_rank(int depth1,int *rand_arr){ if(now_N == N) return ; int depth = depth1; bool i_jump = false; if(depth == 9) { for(int i = 0;i < 9;i++) { A[i] = rand_arr[i]; } build(); return ; } int new_A[9]; for(int i = 0;i < 9;i++) { new_A[i] = rand_arr[i]; } //放置 i //for(int i = 1;i < 10;i++) //for(int i = 8;i > -1 ;i--) for(int i = 1;i < 10;i++) { if(depth == 0) { new_A[0] = 7;//修改学号位置 my_rank(depth+1,new_A); } else { int j; for(j = 0;j < depth;j++) { // if repeat -- break if(new_A[j] == i) { i_jump = true; break; } } if(i_jump == true) { i_jump = false; continue; } new_A[j] = i; my_rank(depth+1,new_A); } }} - 这是数独的构建函数，通过一维数组变化而来
这种方法的具体思路是：首先产生一个大小为9的一位数组，1-9自由排列。①第一行为原始数组顺序②第二行为第一行数组左移三位后的状态③第三行为第二行左移三位后的状态。把原始数组左移一位作为第四行的顺序，依次执行前三步，把原始数组左移二位作为第六行的顺序... ...具体实例如下：| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|
| 4 | 5 | 6 | 7 | 8 | 9 | 1 | 2 | 3 |
| 7 | 8 | 9 | 1 | 2 | 3 | 4 | 5 | 6 |
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 1 |
| 5 | 6 | 7 | 8 | 9 | 1 | 2 | 3 | 4 |
| 8 | 9 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 3 | 4 | 5 | 6 | 7 | 8 | 9 | 1 | 2 |
| 9 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
代码如下：
void build(){ int move[4]; for(int q = 0;q < 3;q++) { if(q != 0) { //左移4位 for(int j = 0;j < 4;j++)//左移4位 { move[j] = A[j]; } for(int j = 4;j < 9;j++)//左移4位 { A[j-4] = A[j]; } for(int j = 5;j < 9;j++)//左移4位 { A[j] = move[j-5]; } } //赋值第 0 3 6行 for(int j = 0;j < 9;j++) { global_arr[q*3][j] = A[j]; } for(int i = 1;i < 3;i++) { for(int j = 0;j < 3;j++)//左移三位 { move[j] = A[j]; } for(int j = 3;j < 9;j++)//左移三位 { A[j-3] = A[j]; } for(int j = 6;j < 9;j++)//左移三位 { A[j] = move[j-6]; } for(int j = 0;j < 9;j++) { global_arr[q*3+i][j] = A[j]; } } } if(global_arr[0][0] == 7)//学号判断 { arr_write(FileName,global_arr); now_N++; }} - 6）测试运行。程序必须是可运行的，展示出程序运行的截图。
这是启动程序并且生成十万个不重复的数独
这是生成的输出到txt文本中数独的截屏
当输入数据非法时会提示错误
- 7）记录在改进程序性能上所花费的时间，描述你改进的思路，并展示一张性能分析图，并展示你程序中消耗最大的函数。
通过Visual Studio Community 2015中的Visual Studio Profiling Tools工具分析原来程序性能，以下为程序运行生成40000个数独的性能分析图：
从以上图中看出，运行生成40000个数独工采集样本19251个，消耗时间在20s左右。因为函数是在层层调用的，所以在显示函数占用cup情况会看到树形的my_rank/build/arr_write，占用最多的基本就是cpp内的函数。从执行单个工作最多的函数来看，也全是内置函数。
从上图也可以看到，耗费cup的函数主要是打开文件与关闭文件。 - 8）在你实现完程序之后，在下述PSP表格记录下你在程序的各个模块上实际花费的时间。
| PSP2.1 | Personal Software Process Stages | 实际耗时（分钟） |
|---|---|---|
| Planning | 计划 | 30 |
| · Estimate | · 估计这个任务需要多少时间 | 30 |
| Development | 开发 | 705 |
| · Analysis | · 需求分析 (包括学习新技术) | 45 |
| · Design Spec | · 生成设计文档 | 30 |
| · Design Review | · 设计复审 (和同事审核设计文档) | 20 |
| · Coding Standard | · 代码规范 (为目前的开发制定合适的规范) | 25 |
| · Design | · 具体设计 | 300 |
| · Coding | · 具体编码 | 250 |
| · Code Review | · 代码复审 | 20 |
| · Test | · 测试（自我测试，修改代码，提交修改） | 15 |
| Reporting | 报告 | 75 |
| · Test Report | · 测试报告 | 15 |
| · Size Measurement | · 计算工作量 | 20 |
| · Postmortem & Process Improvement Plan | · 事后总结, 并提出过程改进计划 | 40 |
| 合计 | 810 |
注：以上为估计时间
-9) 个人总结
这个项目确实耗费了很多时间，远超出了预估，也确实学到了很多东西，特别是在工具使用方面。这个项目起到了工欲善其事，必先利其器的效果。不错。