1）在文章开头给出Github项目地址。（1‘）
2）在开始实现程序之前，在下述PSP表格记录下你估计将在程序的各个模块的开发上耗费的时间。（0.5‘）
| PSP2.1 | Personal Software Process Stages | 预估耗时（分钟） | 实际耗时（分钟） |
|---|---|---|---|
| Planning | 计划 | 60 | 60 |
| · Estimate | · 估计这个任务需要多少时间 | 60 | 60 |
| Development | 开发 | 470 | 490 |
| · Analysis | · 需求分析 (包括学习新技术) | 180 | 120 |
| · Design Spec | · 生成设计文档 | （无） | （无） |
| · Design Review | · 设计复审 (和同事审核设计文档) | （无） | （无） |
| · Coding Standard | · 代码规范 (为目前的开发制定合适的规范) | （无） | （无） |
| · Design | · 具体设计 | 120 | 180 |
| · Coding | · 具体编码 | 120 | 140 |
| · Code Review | · 代码复审 | 20 | 20 |
| · Test | · 测试（自我测试，修改代码，提交修改） | 30 | 30 |
| Reporting | 报告 | 20 | 30 |
| · Test Report | · 测试报告 | （无） | （无） |
| · Size Measurement | · 计算工作量 | （无） | （无） |
| · Postmortem & Process Improvement Plan | · 事后总结, 并提出过程改进计划 | 20分钟 | 30分钟 |
| 合计 |
3）解题思路描述。即刚开始拿到题目后，如何思考，如何找资料的心路历程。（3‘）
分析
这道题要求输出至多10^6个数独终盘有如下方法：
- 用完全随机与深度优先搜索加回溯的方法构造出数独终盘，这样复杂度较高，编程复杂度也很高，而且还要用一个复杂度同样很高的算法，来检验输出的数独是否与之前的数独有相同的，显然不满足需求，思路不对。
- 于是我们换个思路，我们可以按规律构造出数独：
- 让第一行的数字是1到9，第四行是2到9再到1，第七行是3到9再到1和2
- 接下来的空行的数字是上一行对应空格的数字加3（9加1后回到1，9加2后回到2，以此类推）
- 这样构造可以保证满足数独矩阵的要求，并且能在O(1)的复杂度下构造出矩阵。
- 我们让第一行的数字是1到9的全排列，这样子的矩阵有几个呢，有8!个，不足10^6个，怎么办呢，没事，4到6行之间是可以任意互换的，7到9行是可以任意互换的，2、3行是可以任意互换的，这样就有8!乘以72种了，就满足10^6的要求了。
- 接下来还要满足一个随机的条件，我们让第一个矩阵出现的序列是随机生成的就行，具体方法为随机生成一个0到8!-1的数k，然后输出字典序第n大的1到9的全排列。
实现
- 用一个solvecur0()函数生成第一行的序列，此行可构造出72种数独终盘。
- 用solvecur()函数构造出接下来的八行，具体构造出的样式根据它是第一行构造出的第几个终盘。
4）设计实现过程。设计包括代码如何组织，比如会有几个类，几个函数，他们之间关系如何，关键函数是否需要画出流程图？（4‘）
5）代码说明。展示出项目关键代码，并解释思路与注释说明。（5‘）
- void update() {
- cnt=0;
- for (int i=0; i<9; i++) {
- if (arr[i]!=-1) arr[cnt++]=arr[i];
- }
- }
-
- //这个是构造出字典序第num大的1到9的全排列
- void solvecur0(int num) {
- int tot=ALL;
- memset(cur, 0, sizeof(cur));
- cnt=0;
- for (int i=0; i<9; i++) {
- arr[cnt++]=i;
- //arr数组储存当前1到9数字中还没被用到的数字
- }
- cur[0][0]=STARTNUM-1;//第一个数字是学号构造出来的
- arr[cur[0][0]]=-1;//把第一个数去掉
- for (int j=1; j<9; j++) {
- update();//得出下一个数字之前更新arr数组，把用过的数字去掉
- tot/=(9-j);
- int choose=num/tot;
- cur[0][j]=arr[choose];//取出下一个数字
- arr[choose]=-1;//删掉取出的数字
- num-=(tot*choose);
- }
- }
6）测试运行。程序必须是可运行的，展示出程序运行的截图。PS：如果有扩展需求或者更高级的需求，请秀出来，有额外加分。（3‘）
7）记录在改进程序性能上所花费的时间，描述你改进的思路，并展示一张性能分析图，并展示你程序中消耗最大的函数。PS：如果采用Visual Studio Community 2015开发，使用C++或者C#语言实现，VS 2015的性能分析工具可自动生成。（3‘）
消耗最大的函数是输出数独的println()无疑了。
