运行环境: windows7
编程IDE: Visual Studio 2013
编程语言: C++
Github地址:biuibiu~
项目需求
利用程序随机构造出N个已解答的数独棋盘。
输入: 数独棋盘题目个数N(0< N<=1000000)
输出:随机生成N个 不重复的已解答完毕的 数独棋盘,并输出到sudoku.txt中,且左上角的第一个数为:(学号后两位相加)% 9 + 1
解题思路
先初始化一个二维数组sudoku[9][9],再往里面填数字,而第一个数字是规定的,我的值为5,通过回溯调用,分别满足行和列和小九宫格中数独的条件就可以填数字。而在遍历数组的时候回溯调用的关键字count很重要,这是我在查资料时发现的一个很巧妙的地方,附上传送门,假设想x,y来表示坐标时,令x = count/9,y = count%9;则当随着count值的增大,就可以实现9*9宫格的遍历。然后关于输出方面的内容,我选择和其他同学一样的方法,即字符输出方法,节省了很多时间。
遇到的困难及解决方法
-
茫然
刚开始那到题目的时候不知道从何做起,况且在家网络不好,也催生了我的惰性,然后越拖越久,直到来了学校,但是又要补考,又得从新搁浅,我觉得我最大的问题不在技术方面的,而是在于自己的心态,不能摆正好自己的位置,导致一拖再拖。这点一定要做出改变。 -
乱麻
在搜索资料时,发现了好几种算法,有矩阵变换,有填数法和回溯法,我本来是想通过第二种方法来做的,碍于迟迟没有写出代码不得不想另一种方法。然后问了同学的思路,用了回溯法才恍然大悟。 -
短板
vs之前很少用到,所以不得不一边百度一边写,在处理字符串输出的时候遇到了个警告,找到解决方法:“预处理器定义”中加一个_CRT_SECURE_NO_WARNINGS。
设计实现
判断行
for(value = 0; value < 9; ++value)
{
if(sudoku[x][value] == sudoku[x][y] && value != y)//检查行
{
return false;
}
判断列
for(value = 0; value < 9; ++value)
{
if(sudoku[value][y] == sudoku[x][y] && value != x)//检查列
{
return false;
}
判断宫格
int wightx = x/3*3;
int wighty = y/3*3;
int temp;
for(value = wightx; value < wightx + 3; ++value)//检查九宫格里
{
for( temp = wighty; temp < wighty + 3; ++temp)
{
if(sudoku[value][temp] == sudoku[x][y] && value != x)
{
return false;
}
}
}
核心代码--回溯
void backtrace(int count,FILE* fp)//回溯调用
{
if(count == 81)
{
sum++;
if(sum >= num)exit(0);
for(int i = 0;i<9;++i)
{
for(int j = 0;j<9;++j)
{
ch[flag++] = sudoku[i][j]+'0';
ch[flag++] = ' ';
}
ch[flag++] = '\n';
}
ch[flag++] = '\n';
fputs(ch,fp);
flag = 0;
return ;
}
int row = count/9;
int col = count%9;
if(sudoku[row][col] == 0)
{
for(int i = 1;i<=9;++i)
{
sudoku[row][col] = i;
if(Yesdis(count))
{
backtrace(count+1, fp);
}
sudoku[row][col]=0;
}
sudoku[row][col] = 0;
}
else
{
backtrace(count+1,fp);
}
}
测试运行
结果:
性能分析
摘要
一共用了26秒
从代码分析可以看出除以9这个运算占了很大时间,还有就是Yesdis函数也可以有改进的地方。
PSP表
PSP2.1 | Personal Software Process Stages | 预估耗时(分钟) | 实际耗时(分钟) |
---|---|---|---|
Planning | 计划 | ||
· Estimate | · 估计这个任务需要多少时间 | 240 | 1400 |
Development | 开发 | ||
· Analysis | · 需求分析 (包括学习新技术) | 60 | 60 |
· Design Spec | · 生成设计文档 | 30 | 30 |
· Design Review | · 设计复审 (和同事审核设计文档) | 30 | 0 |
· Coding Standard | · 代码规范 (为目前的开发制定合适的规范) | 30 | 0 |
· Design | · 具体设计 | 45 | 30 |
· Coding | · 具体编码 | 200 | 200 |
· Code Review | · 代码复审 | 45 | 30 |
· Test | · 测试(自我测试,修改代码,提交修改) | 200 | 180 |
Reporting | 报告 | ||
· Test Report | · 测试报告 | 20 | 20 |
· Size Measurement | · 计算工作量 | 10 | 3 |
· Postmortem & Process Improvement Plan | · 事后总结, 并提出过程改进计划 | 20 | 30 |
合计 | 930 | 2013 |
学习进度条
第N周 | 新增代码(行) | 累计代码(行) | 本周学习耗时(小时) | 累计学习耗时(小时) | 重要成长 |
---|---|---|---|---|---|
1 | 144 | 144 | 33.5 | 33.5 | 巩固了回溯算法的知识 |
关于执行力、泛泛而谈的理解
执行力是有效利用资源、保质保量达成目标的能力,我觉得这个和一个人的经历和努力有关,如果对既定的目标不付出应有的行动,就成了题目所说的泛泛而谈。那样做又何必呢?所以要努力提高执行力,对自己所说的事所做出的承诺负责到底。然而光说是不管用的,要付诸行动。
泛泛而谈,浮于表面。这是很多人的诟病,有时我也会模棱两可。所以要经常提醒一下自己是否重蹈覆辙了,努力养成一种彻底,坚定的习惯。
转眼就大三了,实感惭愧,从来都没有为了一件事早起努力奋斗过,感觉大学生活一下子就过了一半,我到底来这里追求什么?我也常常这样问自己。老是说要是有高三一半的精神就好了却也只是说说而已,泛泛而谈在我身上明显的印证了。不过最近还好,借着复习补考的势头,坚持了一周多的时间在图书馆晚自习,既然心中已经有了目标,我也要重整旗鼓,扬帆起航了!
最后,一定要养成晚上去图书馆自习看书的习惯!!
end!