我的Github项目地址，使用工具VS2017社区版 / DevC++5.11，开发语言为C语言
基础题要求如下，附加题不会做就不贴出来了...：
项目需求
利用程序随机构造出 N 个已解答的数独棋盘 。
输入
数独棋盘题目个数 N
输出
随机生成 N个不重复的已解答完毕的数独棋盘，并输出到 sudoku.txt中
--引用自《第二次作业——个人项目实战》
一、心路历程
说实话拿个这个作业，不对，应该叫做小项目，我是被吓了一跳。看着这满屏的字，加上Deadline 9月10日，本来基础就差的我顿时慌得要死（还好后来加时3天松了口气）。首先我没有《构建之法》这本书。无奈，火速跑到京东订购一本，然后开始研读项目需求。
我通读了一遍，就知道附加题的GUI界面开发的分我是别想要了，生成终盘数独和唯一解可填充数独还可以拼一拼。但是问题来了，什么是数独呢......我听说过，但是不确定。于是我又跑去百度，证实我的记忆是正确的。确认无误后，我开始想，怎么生成呢，怎么生成呢......坐在电脑前良久没有思路，我就在阳台转啊转。突然我灵光一闪，想到：得出的终盘是随机的，他每个格子的数字都要满足在行、列、宫内不重复出现，也就是说要随机生成数字，一个格子一个格子去填，然后加以条件判断，满足则填入，再下一个。这样，我脑子里飞速的转动，代码的轮廓开始涌现。于是我飞似的回到座位，先填好PSP表格，再打开DevC++，开始编码。
因为只是一个想法，在编写了5个函数（分别是一个接口，和判断行、列、宫数字是否重复的函数，以及一个打印函数）后，我先用的是DevC++来试验一下我的功能模块是否正确（万万没想到的是这居然和《构建之法》提到的单元测试不谋而合）
判断比较简单，下面只展示一下我的接口函数（之所以是a[10][10]，是因为我想使用a[1]~a[9]来表示第1行到第9行）
// 行、列、宫判断函数均为bool型，数字有重复返回false，否则返回true
void sudoku_algorithm(int a[10][10]) // 生成数独的算法
{
srand((unsigned)time(NULL));
for (int row = 1; row <= 9; row++)
{
for (int col = 1; col <= 9; )
{
int rand_num = rand() % 9 + 1;
if(!sudoku_row(a, row, col, rand_num))
continue; // 判断行
if(!sudoku_col(a, row, col, rand_num))
continue; // 判断列
if(!sudoku_mod(a, row, col, rand_num))
continue; // 判断宫
a[row][col++] = rand_num;
//printf("%d ", a[row][i]);
}
for(int i = 1; i <= 9; i++)
printf("%d ", a[row][i]);
//putchar('\n');
}
}
然后我在main()函数 int a[10][10] = {0}，再调用这个函数，结果出现了下面这张图的情况
没错，它卡住了......我检查了前面的数字，发现都满足数独条件，但是到第6行就卡住了......我又尝试了几次输出，发现有时可以完整地输出一个数独！但是有时就和这个一样卡死在某一行。我在心想：不对啊，就这张图来说，我在第6行第一个数字填入4或7是没有问题的啊，为什么？？？马萨卡......
于是我把打印语句换在了里面，每找到一个数字就打印出来，第二个循环外再加个换行。结果和我想的一样，真实的情况应该是这样的
也就是说在某个格子里，rand_num赋值数字1~9填入均不符合数独的条件，这样就会陷入死循环。
怎么办呢？我看着屏幕前的代码，思绪再次打转。我冥思苦想了半天，觉得这样那样也不是办法，索性再加一个test函数，先把1~9的数字全部试一遍，看这个格子能不能填，不能填的话，索性把这一行重置为0，从头开始。说干就干，不一会儿这个函数就写好了，我把它放在了sudoku_algorithm()函数的int rand_num的下面
bool sudoku_test(int a[10][10], int row, int col) // 判断这个格子能否填入 1~9
{
int count = 0;
for (int i = 1; i <= 9; i++)
{
bool flag1 = sudoku_row(a, row, col, i);
bool flag2 = sudoku_col(a, row, col, i);
bool flag3 = sudoku_mod(a, row, col, i);
if (flag1 && flag2 && flag3) // 说明数 i 可以填入格子
break;
else
count++;
}
if (count == 9) // 说明 1~9 都不能填入
{
for(int i = 1; i <= col; i++)
a[row][i] = 0;
return false;
}
else
return true;
}
再次运行之前，我心里并没有底。但令人欣慰的是，这次生成了完整的数独。
高兴之余，我并没有忘记多测几次，以防刚才那种情况。在我把生成的数独数量调到10时，我发现我输出的10个数独时一模一样的！WTF？虽然我每次点运行生成的数独不一样，但数量大于1时所有的数独都一模一样了。我以前见过这种情况，就是没有设置随机数种子或是种子一样所导致的，可我明明设置了啊......我人傻了，这个百度也解决不了，我开始向大神们求助，得到了统一回复就是“我还没做呢，不是还早嘛......”。果然大神们敲这种简单的题目都是几个小时搞定的。我长叹一口气，又试着保存数独的第一个数，并与新生成的数独的第一个数做比较，相同则不输出，重新开始。
我还是蛮高兴这样做的话我生成了不同的数独。但是在控制台，几乎是每隔1秒才输出一个数独，这和之前比简直差远了。但是每隔1秒一个数独让我猜想会不会是随机种子是每隔1秒刷新一次，而我生成数独速度太快导致输出一样的数独。我到CSDN发了一贴，得到了如下回复
srand在哪里？
不能放在循环体内以及循环体内的函数内，因为代码执行速度很快，即便你是在循环体内执行srand(time(0))时间种子基本不会改变导致伪随机数是一样的。 ---By sdghchj
--引用自《随机生成多个数独的程序问题》
这样我的疑问得到解决，就是把srand()函数放到主函数，也就是接口的前面去......（换个位置问题就解决了，这真的是......）
然而事情不可能会那么顺利的，尤其是对我这种菜鸡来说。大概我运行.exe每10次，就会出现最开始那个情况的卡死。我用最开始的方式测试，这次却没有出现卡死在中间的情况，都是卡死在了每一行的第一个格子。然而令我不解的是，明明同样的，我能在这个格子里填入数字，他就是过不去。
一个大胆的想法出现在我的脑海，会不会9！== 362 880 种排列方式在这一行都行不通？我没法一种一种去验证，因为如果是这样我只能说我这个算法实在是烂。于是我只能认为是这样，就给int了一个变量fail_times = 0，每次出现重置行的操作都自加1，当超出一个定值（自己设定，先设置为2000）时，就把上一行也全部重置。这个fail_times设在第一个循环和第二个循环中，以下代码加在第二个循环里
if (fail_times > 2000 && row > 2)
{
for (int i = 1; i <= 9; i++)
{
a[row][i] = 0;
a[row - 1][i] = 0;
row -= 2;
break;
}
}之后经过无数次测试，发现都能生成正确的结果了，我开始把代码放到VS上。按照VS的特性稍作修改，再加入读写文件的函数，开始测试。
我使用DEBUG模式下的性能分析，这样每个函数的调用次数都会显示出来，但结果让我非常不满意。我生成1000个数独耗时是71秒钟（性能分析报告和截图被我误删了），这大大超出了题目要求的“1000个不超过60秒，否则0分”。我将视图调到“函数”模块，发现sudoku_test()调用的次数最多，达到了百万次。而每个test()中在最差的情况下会调用row()，col()，mod()个9次，共计27次，这直接导致了这三个函数调用次数也非常大。
我开始着手修改代码。我想：判断格子能否填数是肯定要判断的，不然之前写的都白费了。但是......嗯，如果这个格子能填数，那么即使随机产生的rand_num不符合要求，那下次也不必再调用sudoku_test()了。于是我bool了一个flag = false，若test()为真，即能填数，则把flag赋值为true，再在test()函数前加一个判断语句，如此即可实现我的想法。这样跑下来，使用性能分析得出的时间是11秒左右。
此外，fail_times上限值对时间也有影响。在if(fail_times>2000)的情况下，程序跑了11秒；在if(fail_times>500)的情况下，程序跑了30秒；在if(fail_times>100)的情况下，却只有6秒。次数再少一些，比如50，时间只有一点点的减少，但是会出现卡死的情况。因此最后我把fail_times的上限值定为了100。
以上展示的代码是编程过程中的思路，完整代码请到我的Sudoku项目下载查看
这之后的工作便是一些修修补补了，比如减少文件打开关闭次数，以及为命令行而修改的版本，如此可以降到5秒，而如果使用DevC++或是命令行执行，生成1000个数独仅仅需要零点几秒的时间。虽然和生成100万个只要30几秒的大神没法比，但能从71秒降到6秒我也很满意了。这些修改过程我都以注释的方式记录在了main.cpp中。
/* 9月11日凌晨更新，修改行、列、宫判断任意一个不满足即执行，而不是全部判断完再执行。如此生成1000个数独，性能分析从5.9秒到4.4秒；命令行生成从0.139秒到0.105秒。观察性能分析的函数表发现，变化较大的是：行判断row()增加了10万次，列判断col()减少了80万次，宫判断减少了150万次（原来全部调用了220万次） */
/* 9月25日早上更新，虽然因为没有认识的人的原因退出了实践课程，但是作业还是按要求修改了，数独左上角的数字已经固定 */
二、测试运行
为了避免打印数独、system("pause")、scanf_s()之类函数对时间的影响，在测试阶段，默认生成1000个数独，且只输出提示信息和打开文件、得到数独、写入数独、关闭文件的时间
结果如下：
三、性能分析与PSP
可以看到的是sudoku_test()依然是占了大头，不过我也想不到什么好方法进行优化了，就暂时先搁一搁吧。
| PSP2.1 | Personal Software Process Stages | 预估耗时（分钟） | 实际耗时（分钟） |
|---|---|---|---|
| Planning | 计划 | 20 | 20 |
| .Estimate | 估计这个任务需要多少时间 | 20 | 20 |
| Development | 开发 | 690 | 510 |
| .Analysis | 需求分析 (包括学习新技术) | 60 | 30 |
| .Design Spec | 生成设计文档 | 120 | 60 |
| .Design Review | 设计复审 (和同事审核设计文档) | 60 | 40 |
| .Coding Standard | 代码规范 (为目前的开发制定合适的规范) | 30 | 0 |
| .Design | 具体设计 | 60 | 40 |
| .Coding | 具体编码 | 180 | 120 |
| .Code Review | 代码复审 | 60 | 20 |
| .Test | 测试（自我测试，修改代码，提交修改） | 120 | 200 |
| Reporting | 报告 | 150 | 80 |
| .Test Report | 测试报告 | 60 | 40 |
| .Size Measurement | 计算工作量 | 30 | 10 |
| .Postmortem & Process Improvement Plan | 事后总结, 并提出过程改进计划 | 60 | 30 |
| 合计 | 860 | 610 |
三、总结
从发布作业的那一刻开始，我就知道暑假已经结束了（虽然我也没回家）。其实如果有思路的话，编码工作其实很快就能完成，即使是我这种所有编程课都在及格线飘过的人。我大部分的时间都花在了熟悉GIT的使用和新的IDE（VS）及其工具上（我还是不知道C怎么用单元测试）。在一次一次的错误和失败中，我用了最笨的方法（打印输出）去找原因，以后或许得学着用DEBUG？在一次一次的代码优化中，切切实实地看到了程序时间的减少。虽然我没法和100万个数独只用30几秒的大佬相比，但对我自己来说，或许就是一种进步了吧。
至于附加题的GUI，实在超出了我的能力。而生成唯一解的未填充数独，我有了思路，就是写一个解数独的模块，然后挖格子，用程序返回他的解的个数，不为1就继续挖。但是遗憾的是我发现我的程序随着格子越来越多，解也越来越多......我问大佬，大佬自己也很忙，故就此作罢了。
| 第N周 | 新增代码（行） | 累计代码（行） | 本周学习耗时(小时) | 累计学习耗时（小时） | 重要成长 |
|---|---|---|---|---|---|
| 0 | 260 | 260 | 11 | 11 | 学会调试、优化方法 |
已为社区贡献13条内容
所有评论(0)