2020软件工程作业03

这个作业属于哪个课程

https://edu.cnblogs.com/campus/zswxy/software-engineering-2017-1

https://edu.cnblogs.com/campus/zswxy/software-engineering-2017-1/homework/10494

这个作业的目标

个人编写程序

作业正文

此文

其他参考文献

www.baidu.com

Github 项目地址

https://github.com/Lesviii/20177694

PSP 表格

PSP2.1	Personal Software Process Stages	预估耗时（分钟）	实际耗时（分钟）
Planning	计划	60	40
Estimate	估计这个任务需要多少时间	60	60
Development	开发	50	60
Analysis	需求分析 (包括学习新技术)	40	40
Design Spec	生成设计文档	40	40
Design Review	设计复审	40	40
Coding Standard	代码规范 (为目前的开发制定合适的规范)	70	60
Design	具体设计	150	120
Coding	具体编码	360	360
Code Review	代码复审	60	60
Test	测试（自我测试，修改代码，提交修改）	50	50
Reporting	报告	60	60
Test Repor	测试报告	30	30
Size Measurement	计算工作量	30	30
Postmortem & Process Improvement Plan	事后总结, 并提出过程改进计划	30	30
合计		1130	1080

解题思路

看到数独宫格题目的时候，由于我从来没有玩过数独。。。所以本人还得先去了解了数独是个什么玩法由于本人实在编程能力太差劲，所以只能去参考带佬的解数独代码，讲实话这个题目看的我人都是晕的。。最开始我是想着对整个x宫格进行一个一个的检查，定义了三维数组，前两维是用来存x宫格的盘面，第三维是用来存这个格子所能填的数字。对每一个各自进行检查，检查这个格子的行和列还有小宫格有哪些数字已经出现过，将其标记。最后检查哪些格子只有一个数字没有被标记就直接将其填入这个格子。然后重复上面的操作。当格子里没有0的时候就停止，输出。之后我通过在网上的学习，学习到了递归的做法，对每个格子可能的数进行尝试，尝试失败就返回来，尝试成功就可以完成了。

设计实现过程

这个题目最关键的解决方法是使用递归回溯

回溯法：是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”

递归回溯部分

对所有格子进行编号n 从0开始从左到右从上到下

以公式法计算每个编号的所在列所在行以及所在小宫的左上角坐标

遍历编号并对为0的格子尝试填入数字1~9

通过Check函数判断填入的数字是否合法如果合法对编号n+1继续深搜下去进行步骤三

不合法退后一位并将编号第n位的格子还原为0

check函数的作用是检查行合法性，列合法性，对于某些特殊阶数独的小宫格合法性

需要判断小宫格合法性的数独通过思考发现计算小宫格左上角坐标的公式

大致的思维导图如下

关键代码展示

1.函数Check：判断该空格待填数字是否符合（行/列/宫）

bool Check(int num, int now_line, int now_column)
{
    for (int i = 0;i < s;++i)
    {
        if (shudu[now_line][i] == num || shudu[i][now_column] == num)
            return false;
    }
    if (block != 0)
    {
        int i, j;
        for (i = now_line / block_line * block_line;i < now_line / block_line * block_line + block_line;i++)
        {
            for (j = now_column / block_column * block_column;j < now_column / block_column * block_column + block_column;j++)
            {
                if (shudu[i][j] == num)
                    return false;
            }
        }
    }
    return true;
}

2.函数Work：递归回溯尝试每一个数字的填入

bool Work(int now_line, int now_column)
{
    if (now_line == s)
    {
        return true;else
    {
        int next_line, next_column;
        next_column = now_column + 1;
        next_line = (next_column == s ? now_line + 1 : now_line);
        next_column = (next_column == s ? 0 : next_column);
        if (shudu[now_line][now_column] != 0)
        {
            if (Work(next_line, next_column)) return true;
        }
        else
        {
            for (int i = 1;i <= s;i++)
            {
                if (Check(i, now_line, now_column))
                {
                    shudu[now_line][now_column] = i;
                    if (Work(next_line, next_column)) return true;
                }
            }
            shudu[now_line][now_column] = 0;
            return false;
        }
    }
}