说明
解题思路
- 一开始拿到的时候,有一个思路,可以先填写全盘的“1”,然后在插空填满全盘的“2”。后来觉得自己理不清那个思路。遂放弃。
参考思路:(http://blog.csdn.net/nibiewuxuanze/article/details/47679927) - 第二个思路,是在一个博客上看到的,博主是把第一行随机打散然后第二行开始,从1-9测试哪一个数能填入此空,继续往下。但是这个思路是有问题的,因为选择填入的数字是一个循环,从1-9,也就是就是一旦第一行确定了,下面的数独只有一个唯一解了,重复率极高。
- 后来改进了,通过rand( )函数随机生成数字然后测试能否填入该空格。测试条件三个:行、列、3x3小方格。
- 为了随机性更强,又改进了一种方式:每次都随机打乱一个初始数组,然后从这个数组里抽选数字考虑是否填入。
random_shuffle(&(vi[1]), &(vi[10]));//vi一维数组打乱1-9
- 对于左上角固定数字的思路,一开始是打算等数独终盘生成后,找到第一个3x3方格里的需要的数字,把该行该列换到第一个。后来觉得这种方法花费的时间很多,修改成了一开始就固定sudoku[1][1]=x。从第二个数开始填写,加快了运行速度,缩短时间。
参考思路:(http://blog.jobbole.com/108488/?utm_source=tuicool&utm_medium=referral)
注意: - 第一行除了第一个固定,其他地方都通过find(i,j)取得k值
- 在选取k值的时候,用一个数组先打乱,再按序从中选取
关键代码
除了主函数外只有两个函数
bool isNUM(string str)//用于判断输入的是否是纯数字
bool find(int i, int j)//搜索(i,j)可以存储的数字
几乎把所有功能都堆在了find(i,j)……发现后面的分析等等很不好做,下一次会注意书写的时候把不同功能拆开,模块化处理。Bool型函数,返回true or false,用sign标识简单明白体现是否能放在某个位置
每次都随机打散数组vi,从随机数组vi中循环挑选数字填写,然后三个判断条件:这一行是否有这个数字、这一列是否有这个数字、这一个3x3小矩阵是否有这个数字。如果都符合,就继续find下一个位置能填入的数字。如果1-9全部尝试了都不符合,就退回上一步。
bool find(int i, int j)//搜索(i,j)可以存储的数字
{
int vi[10];
for (int i1 = 1; i1 <= 9; ++i1)
vi[i1] = i1;
random_shuffle(&(vi[1]), &(vi[10]));//vi一维数组打乱1-9
for (int s = 1; s <= 9; s++)//循环数组取数字
{
int k = vi[s];//取k为数组中第一位数
bool sign = true;//sign标记能否将k放在(i,j)处
for (int m = 1; m < i; m++)
if (sudoku[m][j] == k)//检查同一列是否出现过数字k
{
sign = false;
break;
}
if (sign == true)
{
for (int n = 1; n < j; n++)
if (sudoku[i][n] == k)//检查同一行是否出现过数字k
{
sign = false;
break;
}
}
if (sign == true)
{
int imax = (i / 3) * 3 + 3;//(i,j)所在的3x3小方格的最大行数
int jmax = (j / 3) * 3 + 3;//(i,j)所在的3x3小方格的最大列数
if (i % 3 == 0)
imax = i;
if (j % 3 == 0)
jmax = j;
for (int p = imax - 2; p <= imax; p++)//检查3x3小方格
{
if (sign == false)
break;
for (int q = jmax - 2; q <= jmax; q++)
if (sudoku[p][q] == k)
{
sign = false;
break;
}
}
}
if (sign == true)
{
sudoku[i][j] = k;
if (j < 9)
{
if (find(i, j + 1) == true)//搜索本行右边的位置
return true;
}
else
{
if (i < 9)
{
if (find(i + 1, 1) == true)//搜索下一行
return true;
}
else
return true;//i>=9,j>=9,搜索结束
}
sudoku[i][j] = 0;//找不到要清0
}
}
return false;//本位置1-9都不能填,返回上一步
}
测试运行
错误指令/结果
sudoku.exe -o 1
Sudoku.exe -c abc
Sudoku.exe -c 0正确结果
Sudoku.exe -c 3(9.10更新)发现还要考虑如果传入的参数不等于3个的情况
sudoku.exe -c -c 1
ps:后来发现改成Release的状态下运行速度更快,但是之前测试的版本是Debug的,所以上述的截图上在Debug的文件夹下。
效能分析与改进
- n=1000000
- 解决了大部分的奇奇怪怪的输入输出问题,但是1000000的运行时间还是太久,需要15分钟左右,但是没有想到更好更快的改进方法。并且没有进行重复判断,完全是依赖随机性来避免重复。
- (9.10更新)修改了输出之后,不用ofstream类,用输出重定向,数独缩短了将近一半,现在只需要497s,在十分钟以内。
- (再更新)一开始没有把编译的版本改为Release,所以跑的非常慢,多达857s,超出十分钟。后来优化了一点点的代码,达到497s。将版本改为release之后,速度达到63s。
(舍友的电脑左下角会显示函数名但是我的全都是工程的名字……不知道为什么……)
- 本次作业,自己的代码不够模块化,所有的东西都往一个函数里放,好像这个功能很强大似得。但是其实后面效能分析的时候就比较不容易改进,所以下次码代码的时候,要分块分清楚,更加规范。这次由于在修改输入输出的一些问题花费了很多时间,遂没有去修改函数方面的问题。
命令行执行EXE参考材料:(http://blog.csdn.net/txl199106/article/details/44703489)
PSP表格
PSP2.1 | Personal Software Process Stages | 预估耗时(分钟) | 实际耗时(分钟) |
---|---|---|---|
Planning | 计划 | 20 | 20 |
· Estimate | · 估计这个任务需要多少时间 | 20 | 20 |
Development | 开发 | 660 | 1800 |
· Analysis | · 需求分析 (包括学习新技术) | 60 | 60 |
· Design Spec | · 生成设计文档 | 60 | 120 |
· Design Review | · 设计复审 (和同事审核设计文档) | 60 | 60 |
· Coding Standard | · 代码规范 (为目前的开发制定合适的规范) | 60 | 120 |
· Design | · 具体设计 | 60 | 180 |
· Coding | · 具体编码 | 180 | 240 |
· Code Review | · 代码复审 | 60 | 300 |
· Test | · 测试(自我测试,修改代码,提交修改) | 120 | 720 |
Reporting | 报告 | 60 | 60 |
· Test Report | · 测试报告 | 0 | 0 |
· Size Measurement | · 计算工作量 | 0 | 0 |
· Postmortem & Process Improvement Plan | · 事后总结, 并提出过程改进计划 | 60 | 60 |
合计 | 740 | 1880 |
遇到的困难及解决方法
- 困难描述
1.遇到的最大的困难就是太久没有接触代码了,一开始的时候,简直无从下手,从书柜里翻出了c语言和c++的书,稍微翻了一下,看了几眼头文件什么的。而且,很久没有打代码,思路很混乱,很难切入这个问题,想到核心,进入状态需要很久。
2.二是不熟悉VS。安装花了很长时间在捣鼓,然后关于新建的东西也比较不熟悉,后来是向同学请教了之后才明白具体如何新建。不然之前一直在报错“找不到EXE文件”,搜遍了百度都没法解决……原来是新建的时候建错了文件。并且,对于测试等等,也是第一次接触,一头雾水。一些名词,比如“代码覆盖率”等等都是第一次听说,感觉高大上了不少……
3.对于命令行运行EXE也是第一次接触,花了很多时间看相关的知识,修改主函数。
4.对于单元覆盖率、单元测试还是不熟悉。比起一些大一就用过Github的同学而且我完全是纯新手……一开始有点茫然
- 做过哪些尝试
1.看其他同学写的博客,有的同学会写教程,感觉很赞,比如VS安装教程等等,虽然可能大部分人都会但是……对于比较菜鸟的我还是挺有用的T T。。
2.还有的同学会把觉得不错的教程链接贴出来,我就进去看看,感觉有的写得简单易懂,能一下子理解很多。
3.感觉现在的自己还处于“拿*造车”的阶段,还有很多东西不是真正属于自己的,还需努力。
- 有何收获
1.熟悉了对于命令行运行exe的主函数写法,文件的输出,输出重定向,最重要的是重新拾起了打代码的思维。
2.本次的习题,我觉得和之前上c++的作业还是有很大区别的,因为c++只需要打一个代码就好了,而本次作业,就更接近真正的程序员要做的事了,包括各种测试等等,完成度更高,更完善了,更像是一个项目而不是一段代码了。