github地址:
解题思路分析
刚刚接触到这个题目的时候，就想到了二维数组跟回溯法（虽然不是很熟练），但是从一开始我对数独有个误区，就是宫中不能重复这个问题，我的认知中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 |
总结
- 这次的作业真是突如其来，让我的暑假如此收尾，跟期末一般。说到这次的作业，代码倒不是很难，但是后续的一些工作简直让人发疯，都没有接触过，要下好多插件，最气的是下完后还是没成功。 总的来说还是对这些工具不熟悉，有些是见过没用过，有些是没见过没用过，总之就是很生疏。有点哀伤。