欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

第二次作业——个人项目实战:数独

程序员文章站 2022-03-10 16:05:37
...

运行环境: 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!