1.GitHub地址
**https://github.com/3781/sudoku **
2.解题思路
观察题目输出要求，可以看出解决该问题应该将重点放在"N个”和“不重复”这两个关键词上，"N个”决定了问题的规模，所以要考虑的是算法的效率问题，产生单个数独解的耗时不能太长，而“不重复”也是算法设计过程中必须考虑的一个点。
通过查找资料，产生数独解的方法大多是“回溯法”。该方法需要经过先随机生成一个1到9不重复的序列，再进行尝试性填充，不停的验证，不停的回退，重复验证回退的步骤直到填充结束。可以看出，这种办法产生数独解的效率并不高，因为要做大量的回退操作，而且如果采用该方法，为了达到题目所指的“不重复“要求，那就需要对新产生的解和旧解集合一个个去对比，其消耗的时间也会随着N的增大而变得很长。
考虑到以上情况，所以决定不采用回溯的方法。继续观察数独解的排列规律，发现如果确定了第一个九宫格，那么通过行变换和列变换就能生成其余的九宫格，从而合成一个正确的数独解，这样的话，就可以产生9!=362880个数独解，产生数独解的速度明显快于“回溯法”。举个例子说明算法的实现过程：
(1)产生一个1到9不重复的随机序列(如下面：519483276)，并依次填入第一个九宫格：
5 1 9
4 8 3
2 7 6
(2)接着通过列变换生成左边另外的两个九宫格，如第二个九宫格就是通过第一个九宫格按照第二列、第三列、第一列排列生成：
5 1 9
4 8 3
2 7 6
1 9 5
8 3 4
7 6 2
9 5 1
3 4 8
6 2 7
(3)通过行变换生成剩余的九宫格，如第四个九宫格通过第一个九宫格按照第二行、第三行、第一行排列生成：
5 1 9 4 8 3 2 7 6
4 8 3 2 7 6 5 1 9
2 7 6 5 1 9 4 8 3
1 9 5 8 3 4 7 6 2
8 3 4 7 6 2 1 9 5
7 6 2 1 9 5 8 3 4
9 5 1 3 4 8 6 2 7
3 4 8 6 2 7 9 5 1
6 2 7 9 5 1 3 4 8
3.设计实现
1.题目1
设计了三个类,分别是SudokuData(存储数独解数据)、SudokuGenerator(数独解生成器)、SudokuTest(测试数独解的正确性)。
2.附加题1
使用QT进行GUI的开发，因为加入GUI的因素，所以除了使用上面的三个类，同时引入MainWindow(主游戏窗口类)、SelectNumDialog(选择数字对话框类)。
4.代码说明
/*** getNextMatrix
* 获取下一个数独解
*/
bool SudokuGenerator::getNextMatrix(SudokuData &data)
{
if (mCount == mMatrixNum) {
return false;
}
// 随机产生第一个九宫格
randomFirstMatrix();
// 生成数独解
generate(data);
mCount++;
return true;
}
函数getNextMatrix是调用产生数独解的接口。
/*** randomFirstMatrix
* 随机产生第一个九宫格
*/
void SudokuGenerator::randomFirstMatrix()
{
while (true) {
// 生成随机排列
std::random_shuffle(mFirstMatrix, mFirstMatrix + SudokuData::DIMEN);
std::stringstream ss;
for (int i = 0; i < SudokuData::DIMEN; i++) {
ss << mFirstMatrix[i];
}
std::string str = ss.str();
// 排列是否已经存在，不存在则跳出循环
if (mGeneratedFirstMatrices.count(str) == 0) {
mGeneratedFirstMatrices.insert(std::pair<std::string, int>(str, 1));
break;
}
}
}
该函数通过map来保证产生的第一个九宫格不重复，将数字序列转换成字符串序列，并作为map的键。而random_shuffle是一个对一个数组进行随机打乱的函数，利用该函数产生随机数字序列。
/*** generate
* 根据第一个九宫格的数据，生成数独解
*/
void SudokuGenerator::generate(SudokuData &data)
{
int i, j, k;
int sqrtDimen = SudokuData::SQRT_DIMEN;
// 放入第一个九宫格数据
for (i = 0, k = 0; i < sqrtDimen; i++) {
for (j = 0; j < sqrtDimen; j++) {
data.setData(i, j, mFirstMatrix[k++]);
}
}
int firstRow, firstCol, t1, t2;
// 放入最左边另外两个九宫格数据
for (t1 = 1; t1 < sqrtDimen; t1++) {
firstRow = sqrtDimen * t1, firstCol = sqrtDimen * 0;
for (j = firstCol; j < firstCol + sqrtDimen; j++) {
int col = firstCol + (j + t1) % sqrtDimen;
for (i = firstRow; i < firstRow + sqrtDimen; i++) {
data.setData(i, j, data.getData(i % sqrtDimen, col));
}
}
}
// 放入剩余九宫格数据
for (t1 = 0; t1 < sqrtDimen; t1++) {
for (t2 = 1; t2 < sqrtDimen; t2++) {
firstRow = sqrtDimen * t1, firstCol = sqrtDimen * t2;
for (i = firstRow; i < firstRow + sqrtDimen; i++) {
int row = firstRow + (i + t2) % sqrtDimen;
for (j = firstCol; j < firstCol + sqrtDimen; j++) {
data.setData(i, j, data.getData(row, j % sqrtDimen));
}
}
}
}
}
该函数就是按照解题思路中所讲的通过对第一个九宫格进行列、行的变换生成一个正确的数独解。
/*** randomEmpty
* 随机挖空
*/
void MainWindow::randomEmpty()
{
int i, j;
// 获得一个随机的数独解
SudokuGenerator generator;
generator.setMatrixNum(1);
generator.getNextMatrix(mSudokuData);
// 产生一个长度为81的一维数组a，数组数据为自己的下标，后又使用random_shuffle进行随机打乱
srand(time(0));
const int total = SudokuData::DIMEN * SudokuData::DIMEN;
int a[total];
for (i = 0; i < total; i++) {
a[i] = i;
}
std::random_shuffle(a, a + total);
// 随机生成挖空的数量
mEmptyNum = rand() % 30 + 30;
// 从数组a中取出前mEmptyNum个的数据，即要挖空的点的下标，转换为数独解的行列值后，往挖空处填充0
for (i = 0; i < mEmptyNum; i++) {
int value = a[i];
int row = value / SudokuData::DIMEN;
int col = value % SudokuData::DIMEN;
mSudokuData.setData(row, col, 0);
}
// 保留原始挖空数据，用于清空按钮的还原
mOriginData = mSudokuData;
}
该函数是在附加题1中使用，主要是解决数独解随机挖空问题。
5.测试运行
1.题目1
得到的数独解
2.附加题1
游戏主界面
选择填充的数字
回答错误
回答正确
6.性能分析
这是当N=10000时的性能分析图：
调用关系树
N=1000
N=10000
从上图可以看出randomFirstMatrix函数占用较多的时间，主要是因为当N变大后，random_shuffle产生的随机序列重复出现的可能性加大，所以需要经过更多次的random_shuffle才能产生不重复的解。
7.PSP表格
| PSP2.1 | Personal Software Process Stages | 预估耗时（分钟） | 实际耗时（分钟） |
| Planning | 计划 | 10 | 10 |
| · Estimate | · 估计这个任务需要多少时间 | 10 | 10 |
| Development | 开发 | 350 | 370 |
| · Analysis | · 需求分析 (包括学习新技术) | 30 | 40 |
| · Design Spec | · 生成设计文档 | 50 | 60 |
| · Design Review | · 设计复审 (和同事审核设计文档) | 30 | 30 |
| · Coding Standard | · 代码规范 (为目前的开发制定合适的规范) | 20 | 20 |
| · Design | · 具体设计 | 100 | 120 |
| · Coding | · 具体编码 | 80 | 50 |
| · Code Review | · 代码复审 | 20 | 20 |
| · Test | · 测试（自我测试，修改代码，提交修改） | 20 | 30 |
| Reporting | 报告 | 115 | 135 |
| · Test Report | · 测试报告 | 40 | 50 |
| · Size Measurement | · 计算工作量 | 15 | 15 |
| · Postmortem & Process Improvement Plan | · 事后总结, 并提出过程改进计划 | 60 | 70 |
| 合计 | 475 | 515 |