GIT地址
估计耗费时间：
| PSP2.1 | Personal Software Process Stages | 预估耗时（分钟） | 实际耗时（分钟） |
|---|---|---|---|
| Planning | 计划 | 40 | |
| · Estimate | · 估计这个任务需要多少时间 | 40 | |
| Development | 开发 | 770 | |
| · Analysis | · 需求分析 (包括学习新技术) | 200 | |
| · Design Spec | · 生成设计文档 | 60 | |
| · Design Review | · 设计复审 (和同事审核设计文档) | 30 | |
| · Coding Standard | · 代码规范 (为目前的开发制定合适的规范) | 60 | |
| · Design | · 具体设计 | 150 | |
| · Coding | · 具体编码 | 150 | |
| · Code Review | · 代码复审 | 60 | |
| · Test | · 测试（自我测试，修改代码，提交修改） | 60 | |
| Reporting | 报告 | 210 | |
| · Test Report | · 测试报告 | 150 | |
| · Size Measurement | · 计算工作量 | 30 | |
| · Postmortem & Process Improvement Plan | · 事后总结, 并提出过程改进计划 | 30 | |
| 合计 | 1020 |
解题思路描述：
心路历程
- 本来没选这门课程的，感觉挺难的，后来跟舍友纠结了几天还是在最后的截止日一起压哨选了课，选完就开始赶作业了，希望自己能在这门课中得到提升吧！拿到题目时看到数独有点小熟悉但玩的不多，看到这类题目脑海中的想法就是递归，暴力算法等等。由于自己实力有限，所以肯定会通过查阅资料和请教同学去了解一些相关的算法，通过已经完成的别班同学了解到大部分都用递归回溯，有部分用变换。由于递归也比较符合内心的灵感，所以自己就往这方面去思考。
思路
- 自己的想法是暴力，由于自己水平一般，所以我先试着能够生成一组数独出来，运用递归的算法，在生成的过程中，满足三个判断条件：
- 行数字不重复，
- 列数字不重复，
- 宫（块）数字不重复。
- 第一组数独生成后我开始思考如何继续生成新的数独，最后还是尝试着用简单的回溯替换但可能效率不高的方法，对最后一个数字a下手，将a删除并用[a+1,9]范围的数字替代，如果都无法形成新数独则继续往回推一个数字，按上面方法继续推导，就按这样直到找出符合的那个位置的数字，然后再对其后面的数字进行补充形成新数独。
设计实现过程：
- 我感觉这个算法框架还是挺好组织的，有一个判断函数，有一个生成建立函数，大体框架就有了。在我的代码里也是这样，一个judge判断函数，一个set建立函数。略显简单粗暴。
- 具体是：
- 判断函数里三个判断；
- 在生成函数里我用一个变量做标记，当其等于要求个数时停止输出；
- 首先生成一个数独；
- 生成一个数独后主函数里面进行回溯判断继续生成新数独；
代码说明：
- 判断行、列、宫是否满足要求
//行判断
for (i = 0; i<a; i++)
{
if (c == sudo[i][b])
{
return false;
}
}
//列判断
for (j = 0; j<b; j++)
{
if (c == sudo[a][j])
{
return false;
}
}
//宫(块)判断
m = (a / 3) * 3;
n = (b / 3) * 3;
for (i = m; i<m + 3; i++)
{
for (j = n; j<n + 3; j++)
{
if (c == sudo[i][j])
{
return false;
}
}
}
- 生成函数
void set(int i, int j)
{
int b;
if (out == num)
{
return; //数独个数达到要求个数num时停止
}
for (b = 1; b<10; b++)
{
if (judge(i, j, b))
{
sudo[i][j] = b;
if (j<8) //列小于8时的递归
set(i, j + 1);
if (j == 8 && i<8)
set(i + 1, 0); //列等于8时要选取新的行
if (i == 8 && j == 8) {
for (i = 0; i<9; i++)
{
for (j = 0; j<9; j++)
{
putchar(sudo[i][j] + 48);
putchar(' ');
}
putchar('
');
}
putchar('
');
out++;
}
}
sudo[i][j] = 0;
}
}
- 主函数
int i = 0, j = 0, x = 2, b = 0;
set(i, j);
for (x = 2; x <= num; x++)
{
for (i = 8; i >= 0; i--)
{
for (j = 8; j >= 0; j--) //要再形成一个新数独时，用一个新的数替换原来的数，从sudo[8][8]往回判断
{
for (b = sudo[i][j] + 1; b<10; b++)
{
sudo[i][j] = b;
if (judge(i, j, b)) //原位置数为b,判断b+1~9能否替换原来的数
set(i, j);
break;
}
}
}
}
测试运行：
-
输入数据：
-
输入不合法字符，输出Error：
性能分析：
输出部分原来我用的是cout输出，但跑起来太慢了，后来舍友建议我用putchar，速度提升了不少。
输入100000时：
输入1000000时：
总结：
- 由于在最后才选了课，所以作业有点赶，不过这个周末还是蛮充实的，一直在弄这个作业，少玩了一些游戏，少看了几场英超比赛，但内心却没有什么波澜，毕竟有舍才有得。自己水平不高弄得踉踉跄跄，不过有同学的帮忙自己不懂得地方还是可以及时求解，感谢队友们。希望自己在以后的作业中一步步提高吧。
- PSP
| PSP2.1 | Personal Software Process Stages | 预估耗时（分钟） | 实际耗时（分钟） |
|---|---|---|---|
| Planning | 计划 | 40 | 50 |
| · Estimate | · 估计这个任务需要多少时间 | 40 | 50 |
| Development | 开发 | 770 | 910 |
| · Analysis | · 需求分析 (包括学习新技术) | 200 | 240 |
| · Design Spec | · 生成设计文档 | 60 | 60 |
| · Design Review | · 设计复审 (和同事审核设计文档) | 30 | 30 |
| · Coding Standard | · 代码规范 (为目前的开发制定合适的规范) | 60 | 60 |
| · Design | · 具体设计 | 150 | 160 |
| · Coding | · 具体编码 | 150 | 200 |
| · Code Review | · 代码复审 | 60 | 80 |
| · Test | · 测试（自我测试，修改代码，提交修改） | 60 | 80 |
| Reporting | 报告 | 210 | 240 |
| · Test Report | · 测试报告 | 150 | 170 |
| · Size Measurement | · 计算工作量 | 30 | 30 |
| · Postmortem & Process Improvement Plan | · 事后总结, 并提出过程改进计划 | 30 | 40 |
| 合计 | 1020 | 1200 |