软件工程实践_Task2_sudoku

软工实践_Task2

标签(空格分隔): 软工实践


相关要求第二次作业——个人项目实战

github传送门


解题思路

  • 先是一点杂谈。

  • 首先,看完作业要求之后,心里先有个大概的框架。

    • 语言:C++
    • IDE:本机已安装Visual Studio 2015
    • 效能分析工具:Visual Studio Profiling Tools?善用搜索引擎,下一个。
    • 项目需求:很直观的想法是,一共\(9*9\)个位置,每个位置都随意的填上一个可满足的数,最后形成九宫格。
    • 注意:命令行输入,文件输出,输出格式,\(0<N<=1000000\),左上角的第一个数有特殊要求
    • github:文件组织框架
    • PSP:小说.push(《构建之法》)
    • 暂不考虑附加题
  • 再次细看博客之后,发现一些注意点:

    • 生成的棋盘不重复
      • 一种想法是每生成一个棋盘之后都check一下这个棋盘是否生成过,但是考虑到输入的N的范围,显然这么做过于耗费时间。
      • 换一个路子,既然不能每次都\(check\),那么就得让每次填数的随机性要足够的高。
    • 测试数据中有可能出现错误
      • 注意特殊处理。
    • 使用单元测试对项目进行测试,并使用插件查看测试分支覆盖率等指标。
    • 代码有进展即签入Github
    • 性能分析图,VS 2015的性能分析工具可自动生成。
  • 这样,大概就有个思路,要去怎么实现。结合上述的注意点,考虑到时间、随机性问题,一开始的直观的想法显然需要改进。

  • 考虑第一行,他肯定是一个1到9的排列。

  • 考虑到每个位置只有9种选择,所以每次都rand是不需要的,只要每次从1到9一个个试,check能否填。

  • 考虑到这样子随机性可能不是太好,所以可以再改进一下,每次不必按1到9的顺序去试数,而是将这个试数的序列也随机化,这样子能改善随机性。


设计实现

  • class
    • Sudoku类:
      • 构造、析构函数
      • void SudokuGenerate(); 【publish,生成一个数独】
      • void SudokuPrint(); 【publish,输出一个数独】
      • void getNext(int &i, int &j); 【private,得到下一个位置】
      • bool judge(int row, int col, int curnum); 【private,判断(row, col)这个位置放curnum是否合理】
      • bool dfs(int i, int j); 【private,递归填数】
      • void Generate(); 【private,生成数独】
      • void print(); 【private,输出数独】
  • bool digitCheck(char *s) 【判断当前是否是一个整数】
  • int main(int argc, char *argv[])
    • 从命令行获取输入,调用digitCheck函数判断该输入是否合法。
    • 若输入不合法,输出提示信息。
    • 否则,实例化Sudoku类,调用SudokuGenerate生成一个数独,调用SudokuPrint输出这个数独

代码说明

  • bool Sudoku::judge(int row, int col, int curnum);
    • 判断(row, col)这个位置放curnum是否合理,判断方法为,当前行/当前列/当前块是否已经填过curnum这个数
bool Sudoku::judge(int row, int col, int curnum)
{
// check the col
rep(i, 0, row)
if (sudoku[i][col] == curnum) return false;
// check the row
rep(j, 0, col)
if (sudoku[row][j] == curnum) return false;
// check the area
int belongRow = row / 3 * 3;
int belongCol = col / 3 * 3; // get the upleft of the area
int index = (row % 3) * 3 + (col % 3);
while (--index >= 0)
{
if (sudoku[belongRow + index / 3][belongCol + index % 3] == curnum) return false;
}
return true;
}
  • bool Sudoku::dfs(int i, int j)
    • 递归填数,当(i, j)位置可以填某个数,且填该数可以得到解时,填这个数。
bool Sudoku::dfs(int i, int j)
{
if (i == 9) return true;
for (auto &curnum : trynum)
{
if (judge(i, j, curnum))
{
sudoku[i][j] = curnum;
int _i = i;
int _j = j;
getNext(_i, _j);
if (dfs(_i, _j)) return true;
sudoku[i][j] = 0;
}
}
return false;
}

测试运行

软件工程实践_Task2_sudoku

软件工程实践_Task2_sudoku


性能测试

软件工程实践_Task2_sudoku

软件工程实践_Task2_sudoku

上图的运行参数为【sudoku.exe -c 100000】,可以看到,总执行时间为57.4s,其中SudokuGenerate和SudokuPrint占了较大的比重。


题外话

  • 很绝望啊喂,一回到学校,笔记本就进水GG,项目也还没传github,最后还是在实验室配了半天的VS外加借舍友电脑,匆匆忙忙的写完了基本的作业需求。

软件工程实践_Task2_sudoku

上一篇:图解SQL的inner join、left join、right join、full outer join、union、union all的区别【转载】


下一篇:Oracle 查询用户和删除用户