Github：https://github.com/031502216/softWare
作业地址：http://www.cnblogs.com/easteast/p/7469291.html
PSP 2.1表格
| PSP2.1 | Personal Software Process Stages | 预估耗时（分钟） | 实际耗时（分钟） |
|---|---|---|---|
| Planning | 计划 | -- | -- |
| · Estimate | · 估计这个任务需要多少时间 | 15h | 20h |
| Development | 开发 | -- | -- |
| · Analysis | · 需求分析 (包括学习新技术) | 3h | 5h |
| · Design Spec | · 生成设计文档 | 30min | 30min |
| · Design Review | · 设计复审 (和同事审核设计文档) | -- | -- |
| · Coding Standard | · 代码规范 (为目前的开发制定合适的规范) | 10min | 10min |
| · Design | · 具体设计 | 20min | 30min |
| · Coding | · 具体编码 | 5h | 8h |
| · Code Review | · 代码复审 | 2h | 2h |
| · Test | · 测试（自我测试，修改代码，提交修改） | 2h | 2h |
| Reporting | 报告 | -- | -- |
| · Test Report | · 测试报告 | 45min | 1h |
| · Size Measurement | · 计算工作量 | 15min | 30min |
| · Postmortem & Process Improvement Plan | · 事后总结, 并提出过程改进计划 | 30min | 1h |
| 合计 | 13h30min | 20h40min |
学习进度条：
| 时间 |
新增代码（行） |
本周学习耗时(小时) |
累计学习耗时（小时） |
重要成长 |
|
2017.9.3-2017-9.10 |
200 | 20 | 20 | 对回溯法有了更深的认识，C++挺久没有接触了，这一次写的有些吃力，还有一些以前没有接触过的工具要一步步调试，觉得挺有收获，不过看着自己和有些人在编程这方面确实存在很大差距，所以接下来要加把劲了。 |
| ... |
解题思路：
由于许久没有写过c++，所以感觉很多之前学的知识都已经没有什么印象，只能一点点回忆，慢慢完成本次作业，。在拿到题目后，自己先动手解了一下数独，发现解是可以解出来，但是没有找到特别的好技巧，只能慢慢推理。然后查询了一些专门的解数独教程，方法也是多种多样，但是能够提供解决问题算法的没有太多，后来参考部分的网上资料，大致提供了两种解决方法，分别是回溯和置换。置换法对于本题不太合适，那就使用回溯法。从问题的某一种状态（初始状态）出发，搜索从这种状态出发所能达到的所有“状态”，当一条路走到“尽头”的时候（不能再前进），再后退一步或若干步，从另一种可能“状态”出发，继续搜索，直到所有的“路径”（状态）都试探过。这种不断“前进”、不断“回溯”寻找解的方法，就称作“回溯法”。但是在回溯的过程中怎么样才能将所有符合条件的数独全部输出呢？数独一般都是提供几个数字，然后根据规则填入相应的格子，但是本题是固定了左上角的数字，然后输出满足条件的数独，并非解数独那种单一的解法结构。但是相同的是需要用同一种规则去判断，生成的结果是一个81格的数独。
实现的时候有几个问题：
1.不能生成相同的数独，那么在生成第一个数独以后怎么把第二个数独输出？
2.一个个的按顺序往格子里填写数字，是不是对于性能方面有许多限制，浪费很多时间。
3.看到一些人在使用的时候使用了rand（）这种随机函数，这种方法是否对于生成数独性能上和唯一性上有较大的提升？
综合这些问题，再去寻找答案，心里对于回溯这个方法还是比较认可，也是一个效率相对较高的方法。
设计实现：
代码中有两个函数，back（）回溯函数和Isvaild（）判断放置数字是否合法。
工作流程图：
代码说明：
bool Isvaild(int count) //判断是否合法 { int row = count / 9; int col = count % 9; int j; //同一行 for(j = 0; j < 9; ++j){ if(map[row][j] == map[row][col] && j != col){ return false; } } //同一列 for(j = 0; j < 9; ++j){ if(map[j][col] == map[row][col] && j != row){ return false; } } //九宫格 int Row = row / 3 * 3; int Col = col / 3 * 3; for(j = Row; j < Row + 3;++j){ for(int k = Col; k < Col + 3; ++k){ if(map[j][k] == map[row][col] && j != row && k != col){ return false; } } } return true; }
void back(int k,int request){ //进行回溯 while(1) { int i = k/9; int j = k%9; while(1) { map[i][j]++; if(map[i][j] == 10) { map[i][j] = 0; --k; break; } else if(Isvaild(k)) { ++k; break; } } if(k == 81) { for(int i = 0; i < 9; ++i){ for(int j = 0; j < 9; ++j){ fout<<map[i][j]<<" "; //cout<<map[i][j]<<" "; } fout<<endl; //cout<<endl; } num++; fout<<endl; //cout<<endl; if(num >= request) return; --k; } }
测试运行：
测试运行：
n=1000时
由上述截图可以看出back()回溯函数占用了75%的时间，所占用的比例较重。
在本次作业实现过程中，我是发觉了自己的程序其实是有很大的优化空间的，但是由于时间和能力限制，并没有去实现，但是接下来会去尝试。以下提供一个解决问题的更好的思路可以减少回溯的次数例如dfs深度优先算法还有一个博客推荐的算法跳转链接也可以尝试，都比目前的方法更加优化。在本次的作业中，确实发现自身有很多不足的地方，包括对学术钻研的心态和能力，这是以后要努力的地方。