github地址: https://github.com/Kaloneme/sudoku.git
解题思路分析
刚刚接触到这个题目的时候，就想到了二维数组跟回溯法（虽然不是很熟练），但是从一开始我对数独有个误区，就是宫中不能重复这个问题，我的认知中9x9的数独表中不只有九个宫（之前没了解清楚），而是每9个在一起的格子就是一个宫，这无疑给我添加了巨大的麻烦。后来在跟同学探讨的过程中，他告诉我就只有9个宫，让我的心情一下子放松下来（虽然后面才知道原来代码不是最难过的）。
然后我的思路是先分开宫，然后一行一行填，一个一个填过去，每填一个就检查一次该行、该列、该宫是否有这个数字，要是遇到死胡同，就利用回溯法退回重新。设计过程
语言：c、c++
1.标记函数与初始数独表
int table[11][11]; //数独表
int palace[11][11]; //宫标记
int line[11][11]; //行标记
int list[11][11]; //列标记
int seat[11][11]; //该位置所属的宫 - table是初始表，而palace、line、list都是标记位，seat是点（i，j）位置所属的宫。设计的过程中很容易把数组的值到底表示的是什么搞混了，写着写着就突然混了一下概念，所以我认为之前在纸上的准备很重要，随时可以让你回归最初的概念，比较好分清楚这些东西。
2.初始化函数（给每个位置标记上该位置所属的宫）
shudu::shudu()
{
memset(table, 0, sizeof(table));
memset(line, 0, sizeof(line));
memset(list, 0, sizeof(list));
memset(palace, 0, sizeof(palace));
flag = false;
sum = 0;
for (int i = 1; i <= 9; i++)
{
for (int j = 1; j <= 9; j++)
{
int row = (i - 1) / 3;
int cow = (j - 1) / 3;
seat[i][j] = row + cow * 3 + 1; //标记宫
}
}
}- 最初的想法是把宫分类，然而怎么把分好类的宫与每个位置对应上呢？要是对应上了，这样对于宫是否重复的判断就提供了极大的便利，最后就有了seat二维数组，并且有了这个推算每个位置所属的宫的算式，方便了之后的宫判断，极大的简化了代码的复杂度，顺便把初始表table与其他标记数组初始化。
3.生成数组表（fillNumber（）函数）
/*
利用fillNumber算法，从第二个填起，生成1-9的随机数，每填一个都检查一次是否与
所填的位置的宫、行、列有重复，没有重复就继续，若有重复则将此数加1继续尝试，
填到最后一位时若不符合则逐一退回，直到完成数独表。
*/
void shudu::fillNumber(int x, int y)
{
if (flag)return;
if (x < 9 || y < 9){
int a = x;
int b = y + 1;
if (b>9)
{
b = 1;
a++;
}
int p = seat[a][b]; //p来表示现在所属的宫
int them = rand() % 9 + 1; //产生随机数
int k = them;
while (1){
if (!line[a][k] && !list[b][k] && !palace[p][k]){ //若没出现过则都为0
table[a][b] = k, line[a][k] = 1, list[b][k] = 1, palace[p][k] = 1;
fillNumber(a, b);
table[a][b] = 0, line[a][k] = 0, list[b][k] = 0, palace[p][k] = 0;
}
k++;
if (k == 10)k = 1;
if (them == k)break; //退回
}
}
else{
sum++;
int i, j;
for (i = 1; i <= 9; i++){
for (j = 1; j <= 9; j++){
cout << table[i][j];
if (j < 9)cout << " ";
}
cout << endl;
}
if (sum != n)cout << endl;
if (sum == n)flag = true; //输出n个数独表后结束
}
}- 这里利用fillNumber函数生成整个数独表，在这里，这些用于标记的数组派上了很大的用场。刚开始对于回溯法其实还不是很顺手，在同学的帮助下，才能是顺利的写出了这个算法。不过最后还是遇到一些问题，通过不断插入输出的办法，终于找到问题所在（个人感觉这办法还是很好用的）。不过在这个过程中我了解到自己的薄弱点的所在，虽然知道用这种方法，但是却用不熟悉，还是同学的帮助让我完成了，所以今后，一定要加大码量，加强练习。
性能测试分析
如下图：
这是用cout输出的结果，数组table使用int型，却用了快要两分钟，cpu测试达到了100000。
这是用putchar输出的结果（听同学说用这个会比较快），数组table使用char类型，只用了29秒，cpu测试达到14000+，这也差太多了，有点搞不懂。
| PSP2.1 | Personal Software Process Stages | 预估耗时（分钟） | 实际耗时（分钟） |
|---|---|---|---|
| Planning | 计划 | 50 | 45 |
| · Estimate | · 估计这个任务需要多少时间 | 120 | 130 |
| Development | 开发 | 300 | 360 |
| · Analysis | · 需求分析 (包括学习新技术) | 60 | 180 |
| · Design Spec | · 生成设计文档 | 0 | 0 |
| · Design Review | · 设计复审 (和同事审核设计文档) | 0 | 0 |
| · Coding Standard | · 代码规范 (为目前的开发制定合适的规范) | 10 | 10 |
| · Design | · 具体设计 | 45 | 50 |
| · Coding | · 具体编码 | 60 | 60 |
| · Code Review | · 代码复审 | 60 | 70 |
| · Test | · 测试（自我测试，修改代码，提交修改） | 45 | 60 |
| Reporting | 报告 | 45 | 30 |
| · Test Report | · 测试报告 | 0 | 0 |
| · Size Measurement | · 计算工作量 | 5 | 5 |
| · Postmortem & Process Improvement Plan | · 事后总结, 并提出过程改进计划 | 30 | 45 |
| 合计 | 830 | 985 |
总结
- 这次的作业真是突如其来，让我的暑假如此收尾，跟期末一般。说到这次的作业，代码倒不是很难，但是后续的一些工作简直让人发疯，都没有接触过，要下好多插件，最气的是下完后还是没成功。
总的来说还是对这些工具不熟悉，有些是见过没用过，有些是没见过没用过，总之就是很生疏。有点哀伤。