项目简介
Github链接:https://github.com/fagen/sudoku
1、项目要求
- 能够生成1-1e6个不一样的数独终局并输出到文件 (命令：sudoku.exe -c abc )
- 能够从文件里读取数独问题并将求解结果输出到文件 (命令：sudoku.exe -s path)
- 附加要求：为数独游戏生成一个GUI界面，能够生成任意数量的数独题目并依次显示，棋盘挖空数目30<=n<=60。用户可以在界面上点击或者输入完成数独题目，用户完成数独题目后可以得到反馈，知道自己的题目是否做对
2、PSP表格
3、解题思路及过程
看到题目发现是数独的时候觉得不会太难，只要解决了生成合格的数独终局这个问题，解数独和生成数独问题都是基于相同的规则下产生的。关于游戏界面的添加则是另外一个问题，只是可能会繁琐且耗时一点。
3.1 数独终局生成解决过程
1、暴力法
在没有查询资料的前提下，只了解到一个完整的数独终局规则：在一个99的数字表格中，每一行，每一列，每一个33的9个数字中，都必须包括1-9且不能重复。可以通过随机数逐步产生数字一边检查一遍生成终局。但这个方法由于生成一个终局的过程中每产生一个随机数的同时，都必须检查一遍目前终局的合法性。即使通过一定方式尽量避免检查这个问题，检查次数还是不少。在需要生成1e6个终局情况下还需要进行反复查重，虽然生成终局的质量很高，但是非常浪费时间。
2、全排列+行变换
通过网上查询关于数独终局的生成方法，发现一种较为简便的方式。
对于一个数独终局，在第一行固定了的情况下，从第二行开始，每行在第一行左移3、6、1、4、7、2、5、8的情况下，就可以生成合格的一个数独终局。由于数独终局的第一个数字已经固定为5，所以通过对第一行进行全排列的方式就可以产生8！= 40320种终局。在每一个终局的基础上，通过任意交换2 3行，4 5 6行，7,8,9行就可以产生新的终局。由此总共可以产生403202！3！*3！= 2903040种不同的终局。已经远远超过了题目要求。
代码思路
为了生成足够多的数独终局并且保证不能重复，第一步就是全排列。全排列本可以通过递归生成，但突然想起C++有一个函数next_permutation() 可以完成这件事，因此解决了全排列的问题。
对于每一个全排列，都只确定了第一行，但因为后面8行都是通过第一行平移产生的，因此，一个全排列就确定了一个数独终局。在一个终局的基础上，其他终局的产生只是调换第一个终局行的顺序的产物。为了省去行交换的时间，新的终局的生成只需调换行的输出顺序就可以了。
由于整个过程的代码量不多，并且终局的生成和输出是结合在一起的，于是一个函数就可以解决数独终局的生成问题
同样也是为了效率，整个编码过程基本是使用C语言完成
关于输出以及改进过程
- 二维数组存储81个数字，终局生成之后，采用freopen() 结合putchar() 对字符进行一个一个输出，在每个数字之后输出一个'\0'或者'\n'确保输出格式符合题目要求。通过这样的方式，一个数独终局需要输出163次，生成1e6个数独终局的时间为28s
- 通过对性能分析图的观察，发现整个数独生成过程中，全排列消耗的时间不到1%，而整个函数也没有其他多余的部分，说明，95%以上的时间消耗都是在输出过程中。于是，在输出之前，通过字符连接运算将每一个数字字符和空格和回车提前连接成一个字符串，于是一行只需要输出一次，使用freopen()和puts()，一个数独终局只需要输出10次，虽然运算代价稍有增加，程序运行时间仍然大大减少，从28s减少到了8s。性能得到了很大的优化。
- 继续在输出上做文章，前面的字符串连接主要是空格，但实际上可以把空格提前放入运算的数组中。一开始一位会很麻烦，但只要对代码进行微调就可以了，把循环变量的“i++”改成“i+=2”，同时其余细节进行稍微调整。最终采用freopen()和puts()一次输出一行，不需要进行字符串连接，最终时间是5.5s左右。
- 通过不断尝试，发现使用fopen()函数和fputs()会使得输出的时间稍微有所降低，但是效果不是很明显。
- 终局生成之后，在输出之前将整个熟读终局的所有字符连接成一个长的字符串，于是一个数独终局只需要输出一次。运行时间减少到了3.5s，当电脑状态好的情况下，可以跑进3s
- 在整个改进过程中，发现一个现象，当数组的每一行的所有字符都有效即每一行的末尾都没有'\0'字符的情况下，当用fputs()进行输出时，一次就可以将整个数独终局全部输出。因此有一个设想：使用得当的情况下，不需要进行将163个字符连接成一个长的字符串操作就可以直接输出，预计时间可以节省0.5s左右。但由于代码结构的原因，必须进行较大改动才能实现，故没有尝试。
- 开一个全局数组用于输出，将所有的终局都存进去，在最后需要输出的时候直接一次输出，最终生成1e6终局的时间在2.5s
整个改进过程大概花了5天的时间，平均一天2小时。
关键代码
void sudoku_generate(int n)
{
//char str[30];
char line[9] = { '5','1','2','3','4','6','7','8','9' };
char line1[19] = { '5',' ','1', ' ' ,'2', ' ','3',' ','4', ' ','6',' ','7',' ','8',' ','9','\n','\0' };
int shift[9] = { 0,6,12,2,8,14,4,10,16 };
int pos1[6][3] = { { 3,4,5 },{ 3,5,4 },{ 4,5,3 },{ 4,3,5 },{ 5,4,3 },{ 5,3,4 } };
int pos2[6][3] = { { 6,7,8 },{ 6,8,7 },{ 7,6,8 },{ 7,8,6 },{ 8,6,7 },{ 8,7,6 } };
char final[10][19];
int i, j, k;
int flag = 0;
char str[200];
for (int i = 0; i < 9; i++)//初始值置空格和\0
{
for (int j = 0; j < 17; j++)
{
final[i][j] = ' ';
}
final[i][17] = '\n';
final[i][18] = '\0';
}
final[9][0] = '\n';//第10行只有一个空行
final[9][1] = '\0';
//freopen(SUDOKUPATH, "w", stdout);
FILE *fp = fopen(SUDOKUPATH, "w");
do//生成第一行
{
for (int i = 0; i < 9; i++)
{
line1[2 * i] = line[i];
}
memcpy(final[0], line1, sizeof(line1));
for (i = 1; i < 9; i++)//以第一行为基础，生成一个终局
{
for (j = 0; j < 18; j += 2)
{
final[i][j] = line1[(j + shift[i]) % 18];
}
}
//在一个终局的基础上改变4-6,7-9行的输出顺序即可
for (i = 0; i < 6; i++)
{
for (j = 0; j < 6; j++)
{
str[0] = '\0';
flag++;
for (k = 0; k < 3; k++)//前三行
{
//fputs(final[k], fp);
strcat(str, final[k]);
}
for (k = 0; k < 3; k++)//3 4 5行
{
//fputs(final[pos1[i][k]], fp);
strcat(str, final[pos1[i][k]]);
}
//if (n > 1)
//{
for (k = 0; k < 3; k++)
{
//fputs(final[pos2[j][k]], fp);
strcat(str, final[pos2[j][k]]);
}
//fputs(final[9], fp);//输出回车
strcat(str, final[9]);
if (n == 1)str[161] = '\0';
fputs(str, fp);
n--;
if (!n) { fclose(fp); return; }
}
}
} while (next_permutation(line + 1, line + 9));
}
性能分析图
通过观察分析图可以发现，整个运行过程中，全排列占用的时间仅为0.78%，用于字符串连接的实践也仅有0.15%，说明大部分时间还是消耗在文件输出的过程中，如果要进行下一步的优化，还是应该针对输出部分做改进。
3.2数独求解
求解思路
数独的求解，根据数独终局的特性，最容易想到的就是深度优先搜索的暴力求解，并且代码比较简单，如果采用递归的话。
但很显然，这种解题方式解决少量题目的时候时间上不会有明显的差异。当当解决到1000题的时候，整个过程就会需要20多秒，因此剪枝就很有必要了
剪枝过程
对于数独终局的每一个位置，都代表递归过程中的一层，每次确定当前位置的数字之前，通过遍历当前行、当前列、以及当前3*3网格中的数字，就可以排除不符合条件的数字，从而达到剪枝的目的。
剪枝的过程其实已经完成了对当前数独的合法性的检查
剪枝效果
剪枝之后，解决1000题的运行时间减少了三分之二，从20s减少到了7s左右。
数独求解代码
void settle(int pos)
{
if (pos == 162)
{
settle_flag = 1;
return;
}
int i, j, k;
i = pos / 18;
j = pos % 18;
bool point[10] = { false };
if (ques_board[i][j] == '0')
{
prune(i, j, point);
for (k = 1; k <= 9; k++)
{
if (point[k])continue;
ques_board[i][j] = k + '0';
//if (check(i, j))
{
settle(pos + 2);
}
if (settle_flag) { return; }
ques_board[i][j] = '0';//??
}
}
else
{
settle(pos + 2);
}
if (settle_flag) { return; }
}
剪枝关键代码
void prune(int i, int j, bool point[10])
{
for (int k = 0; k < 18; k+=2)//行排除
{
if (ques_board[i][k] != '0'&&k != j)point[ques_board[i][k] - '0'] = true;
}
for (int k = 0; k < 9; k++)//列排除
{
if (ques_board[k][j] != '0'&&k != i)point[ques_board[k][j] - '0'] = true;
}
int m = 0, n = 0;
if (i / 3 == 0)m = 0;
else if (i / 3 == 1)m = 3;
else if (i / 3 == 2)m = 6;
if (j / 6 == 0)n = 0;
else if (j / 6 == 1)n = 6;
else if (j / 6 == 2)n = 12;
for (int c = m; c < m + 3; c++)
{
for (int d = n; d < n + 6; d+=2)
{
if(c!=i&&d!=j&&ques_board[c][d]!='0')point[ques_board[c][d] - '0'] = true;
}
}
}
解题性能分析图
观察解题性能分析图可以发现，整个解题过程中，一半时间都是消耗在了剪枝，另外一半则消耗在深搜的部分。若是要继续优化，需要考虑不同的剪枝策略，在剪枝时间和效率之间取得一个平衡。
3.3 数独问题生成
问题生成部分是为了后续的GUI做准备，为数独游戏提供合适的题目源。
因为是通过随机挖空实现题目生成，需要数独终局生成作为前提，通过从终局的文件中读取数据，再进行题目生成
题目生成的要求
- 棋盘上挖空不少于30个，不多于60个
- 每个3*3棋盘中挖空不少于2个
规范棋局示例
生成方法和思路
- 先再每个3*3中随机删除2个数字，达到第二个要求，可以挖空18个
- 还需要再挖空12-42个，可以通过生成一个再该区间的随机数n，继续从剩余数字中随机挖空，知道达到预设的要求
生成性能
生成1e6的高质量的数独终局10s以内就可以完成。
问题生成关键代码
void ques_generate(int ques_num)
{
FILE *fpQues1;
FILE *fpBase1;
char str[200];
fpBase1 = fopen(SUDOKUPATH, "r");
fpQues1 = fopen(QUESPATH, "w");
ques_board[9][0] = '\n';
ques_board[9][1] = '\0';
while (ques_num--)
{
str[0] = '\0';
for (int i = 0; i < 9; i++)
{
fgets(ques_board[i], 20, fpBase1);
}fgetc(fpBase1);
//int base[9] = { 0,3,6,27,30,33,54,57,60 };
int base[9] = { 0,6,12,54,60,66,108,114,120 };
//int plus[9] = { 0,1,2,9,10,11,18,19,20 };
int plus[9] = { 0,2,4,18,20,22,36,38,40 };
for (int k = 0; k < 9; k++)//每个3*3随机掏空2个
{
int i, j,
hole[2];//3*3里面掏的位置
hole[0] = rand() % 9;
//hole[1] *= 2;
hole[1] = rand() % 9;
//hole[2] *= 2;
while (hole[0] == hole[1])//防止重复
{
hole[1] = rand() % 9;
}
for (int t = 0; t < 2; t++)
{
int dot;
dot = base[k] + plus[hole[t]];
i = dot / 18;
j = dot % 18;
ques_board[i][j] = '0';
}
}
//已经掏空了18个
int others;
others = 12 + rand() % 31;//再掏12-41个就可以了
while (others--)
{
int k = rand() % 81;
int i = k / 9;
int j = k % 9;
j *= 2;
if (ques_board[i][j] != '0')ques_board[i][j] = '0';
else others++;
}
//freopen(QUESPATH, "w", stdout);
for (int i = 0; i < 10; i++)
{
strcat(str, ques_board[i]);
}if (!ques_num) str[161] = '\0';
fputs(str, fpQues1);
}
fclose(fpBase1);
fclose(fpQues1);
}
3.4 单元测试
主要针对命令行参数的处理以及数独生成器部分进行单元测试，总共设计了10个用例，利用visual Studio 的单元测试功能进行测试。
测试过程中发现的问题：生成0个数独终局的测试一开始没有通过。经过查看代码发现，生成器部分每次都是先进行一次循环，然后再进行判断，跟do...while的逻辑一致，通过提前加一次判断问题得以解决。
关于代码覆盖率
由于VS版本受限，无法完成代码覆盖率测量
4、附加：数独游戏GUI
【题目要求】
- 为数独生成器做一个GUI界面，初始化棋局并将数独题目依次显示
- 用户可以在界面上通过点击或输入完成数独题目
- 用户完成数独题目后可以得到反馈，知道自己的题目是否做对
代码实现
GUI的部分是用C#完成的，数据处理部分通过调用生成器的exe可执行程序。
图形化界面效果
整个界面室是由81个TextBox，和4个Button组成。
工作流程
- 初始化界面
- 点击开始游戏，调用sudoku.exe 生成数独终局，和数独题目。
- 从生成文件中读取数据，初始化棋盘
- 用户填入数字，点击提交获取解答正确或者错误的提示
- 点击下一题，行文件中读取新的数独题目，生成新的棋盘。
