数独

xiaoxiao2021-02-28  35

(1)GitHub链接:https://github.com/htj123?tab=repositories

(2)PSP表格:

PSP2.1

Personal Software Process Stages

预估耗时(小时)

实际耗时(小时)

Planning

计划

2

1.5

Estimate

估计这个任务需要多少时间

2

3

Development

开发

5.5

6

Analysis

需求分析(包括学习新技术)

10

14

Design Spec

生成设计文档

3

2.5

Design Review

设计复审(和同事审核设计文档)

0.5

1

Coding Standard

代码规范(为目前的开发制定合适的规范)

1

2

Design

具体设计

2

2.5

Coding

具体编码

8

10

Code Review

代码复审

1

2

Test

测试(自我测试,修改代码,提交修改)

10

9

Reporting

报告

4

3

Test Report

测试报告

2

2

Size Measurement

计算工作量

2

3

Postmortem & Process Improvement Plan

事后总结,并提出过程改进计划

1.5

1

 

合计

54.5

68

 (3)解题思路及资料查找:

刚刚开始看到数独这个题目,我当时感觉要凉了,因为我以前没有玩过数独也没有接触过关于数独的任何知识,一切都得从头开始,所以还去百度了一下数独的规则以及历史。

接着看到任务的要求,对于我这种只会c的人来说,什么文件操作,什么GitHub,什么性能测试工具(电脑上面连个VS都没有)等等,瞬间感觉原地爆炸了,但是我还是认真去钻研学习,感觉收获还是蛮多的,欢迎有大佬来与我探讨。

数独的历史以及规则:

数独是源自18世纪瑞士的一种数学游戏。是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字,推理出所有剩余空格的数字,并满足每一行、每一列、每一个粗线宫(3*3)内的数字均含1-9,不重复。

数独盘面是个九宫,每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件,利用逻辑和推理,在其他的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只出现一次,所以又称九宫格    ——摘自百度百科

4 5 6 7 8 9 1 2 31 2 3 4 5 6 7 8 97 8 9 1 2 3 4 5 69 1 2 3 4 5 6 7 86 7 8 9 1 2 3 4 53 4 5 6 7 8 9 1 28 9 1 2 3 4 5 6 75 6 7 8 9 1 2 3 42 3 4 5 6 7 8 9 1

数独终局的生成:最多要求1e6的数独终局,根据自己的一些演算,发现给定一个数独,还是有一定的规律可以探寻。左上角的数字给定的情况下(学号末尾两位相加%9+1),那么一个数独根据排列组合的知识,8!=40320,所以我们只需要找出大约25个数独的模板就可以,4~6,7~9这两组可以行内相互调换位置,所以有3!3!=36>25,这样就可以满足生成数独终局的条件了,这个方法我感觉很不错,常规的一般思路都是采用暴力搜索加上回溯判断进行的(我也采用的这样的方法)。

对于数独的求解我的方法就比较暴力,属于那种暴力求解的方法,和一般的思路差不多,回溯进行判重,详细可以参考https://blog.csdn.net/flueky/article/details/51098448。

(4)我在设计实现时,主要的难点在于对于新的技术或者说软件的熟悉运用与学习,代码方面我采用的是暴力的方法求解,判断每一个位置所有可能的结果,然后进行判断,借此来生成数独终局和求解,判断主要利用递归回溯进行的。

根据数独的规则,我主要封装了几个函数,判断小的九宫格,判断行和列,然后就是一些常规的转换函数,因为在进行求解和终局生成时,都要用这些函数进行判断,所以我将使用较多的功能封装成函数,这样用起来很方便,同时也方便自己进行代码的调试,设置了一个总的判断函数,将函数内部的三个判断进行模块化设计。对于数独求解就直接一个函数完成的其功能。

int roldecide(),  int rowdecide(),  int decide(),  int judge(),分别是行列小九宫格以及总的判断函数。

(5)消耗最大的应该是我的判断函数,因为在数独终局生成时每次都需要通过调用判断函数进行判断。

(6)//九宫格判断

//九宫格判断 int decide(int i,int j,int k){    int flag=1;    int l = (i / 3) * 3 + 3;//特殊情况超出小宫格取模    int r = (j / 3) * 3 + 3;      if (i % 3 == 0) l = i;             if (j % 3 == 0) r = j;    for (int t = l - 2; t <= l; t++)  //检查小宫格中是否有相同的数字    {        for (int m = r - 2; m <= r; m++)        {            if (shuDu[t][m] == k)            {                flag = 0;                break;            }        }    }    return flag;}

在进行九宫格判断时由于第一次没有考虑特殊的情况导致上下界限取错误,经过和同学探讨交流,才意识到错误,我认为在小的九宫格进行判断时,需要注意超出的情况。

(7)(2)中的PSP已经记录了总的时间。

转载请注明原文地址: https://www.6miu.com/read-2626787.html

最新回复(0)