这个作业属于那个课程

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

这个作业的要求在哪里

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

这个作业的目标

实现一个命令行程序，不妨称之为Sudoku。

作业正文

https://www.cnblogs.com/liutaodashuaige/p/12539391.html

其他参考文献

www.baidu.com</br>https://www.cnblogs.com/ouyangpeng/p/8537616.html</br>https://blog.csdn.net/sunyanxiong123/article/details/76401590</br>https://github.com/zxw0621/demo/blob/master/20177596/src/sudoku.py

一、GitHub url：https://github.com/liutaodashuaige/LT_DEMO/tree/master/20177569

二、PSP表格

三、解题思路

1.理解问题

• 该算法题的需求是实现一个称之为Sudoku命令行程序。
• 程序要实现利用逻辑和推理，在在数独盘面的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只出现一次。
• 输入要求输入文件名以命令行参数传入。
• 输出要求输出n个程序解出的盘面，每两个盘面间空一行，每个盘面中，每两个小格之间有一个空格。

2.思考如何实现

• 由于不同阶的数独盘面虽然空格数量上有差异，但对每一个空格合法性的判断方法和区块的构造都是相似的，同时这是一个查找最优策略的问题，因此我认为应该使用递归的方式解题。

3.寻找参考资料

• https://github.com/zxw0621/demo/blob/master/20177596/src/sudoku.py#L153
• https://github.com/changorz/work/blob/master/20177583/src/Sudoku.java
• https://blog.csdn.net/sunyanxiong123/article/details/76401590
• GitHub操作参考博客
• PSP表格设计参考

四、设计实现过程

1.函数模块的设计

• 根据本题的解题要求和思考中确定的递归解题思想，应设计以下模块：
  • 主函数模块
  • 递归查找模块
  • 合法性判断模块
  • 输出文件生成模块

2.具体功能函数设计

• main(argv)函数

  • 接受命令行参数，并进行解析
  • 读取input文件，并进行解析
  • 根据盘面数量调用DFS()深度优先搜索递归函数

• DFS(i, x, y)函数

  • 对当前递归状态进行判断
  • 对当前坐标格状态进行判断
  • 尝试填入数值，并调用judge()函数验证其合法性
  • 根据不同条件进行递归
  • 验证失败时，回溯

• judge(i, x, y)函数

  • 对传入的坐标进行行列重复判断
  • 对传入的坐标进行区块定位
  • 对传入的坐标进行区块重复判断
  • 根据是否合法返回布尔值

• MY_OTP(i)函数

  • 根据传入的盘面序号将该盘面矩阵写入output文件

• 简单流程图

3.全局变量设置

• M（盘面阶数）
• N（盘面数目）
• MY_MAPS（储存所有盘面矩阵的三维列表）
• op（文件对象）

五、改进思路

1.代码静态分析

• 首先我们使用pylint进行代码静态分析

很明显代码已经是炸了，不过比起第一次用pylint已经好不少了...第一次可是负分XD

• 让PyCharm帮我整理一下...

看下效果，有所进步，剩下的就是命名的规范了

• 修改不符合规范的命名后

经过一阵捣鼓评分提升了不少，但仍然没有达到满分，测试了一下代码正常运行 只能说，有时候投降不失为一种优雅的退场，我就不折磨自己了 <br/>

2.代码性能优化

1#改为直接给予参数，而不是从命令行接受
2if __name__ == '__main__':
3    # sys.argv[1:]为要处理的参数列表，sys.argv[0]为脚本名，因此弃之不用
4    #main(sys.argv[1:])
5    main(['-m', '9', '-n', '2', '-i', 'input.txt', '-o', 'output.txt'])

• 利用PyCharm的profile进行代码性能分析

显然对于我来说这个图是天书 <br/>

由此表中可得知被调用次数最多和耗时最多的是judge()合法性判断函数和_DFS_()递归函数

• 性能优化集中于judge()和_DFS_()两个函数

3.单元测试

• 函数judge()有返回值，并且是一个布尔值，对该函数进行单元测试

• 卡了很久，一直无法导入py文件的函数，通过参考资料中的方法解决了

• 涉及到全局变量，先对judge()函数进行一些调整，添加一段代码

  1M = 9
  2MY_MAPS = []
  3# 上面都是给judge()函数运行提供必要的全局变量
  4with open('output.txt', 'r', encoding='utf-8') as _fp_:  # 此处直接读取已解矩阵用来判断合法性
  5    _MYMAP_ = []
  6    for line in _fp_.readlines():
  7        if line != '\n':  # 用换行符分割矩阵
  8            _MYMAP_.append(list(map(int, line.strip().split(" "))))
  9        else:
  10            MY_MAPS.append(_MYMAP_)
  11            _MYMAP_ = []
  12    MY_MAPS.append(_MYMAP_)  # MY_MAPS是集合了所有数据的三维数组
  13#单元测试时用来提供全局变量...
  14
  15#################
  16#global M, MY_MAPS
  17# 行列不重复判断
  

• 测试代码编写

  import unittest from Sudoku import judge

  class test_judge(unittest.TestCase): def test_myfun(self): test_num = judge(0, 1, 2)#测试数值 self.assertEqual(test_num, 1)#期望值

  if name == 'main': unittest.main()

• 测试结果

GOOOOOD！测试符合预期结构

4.对代码全面检测和优化后，更新GitHub上的仓库

六、代码说明

0.导包和定义全局变量

1# -*- coding: UTF-8 -*-
2import sys
3import getopt
4
5# 全局变量
6M = ""
7N = ""
8MY_MAPS = []
9OP = ""

1.主函数

1if __name__ == '__main__':
2    # sys.argv[1:]为要处理的参数列表，sys.argv[0]为脚本名，因此弃之不用
3    main(sys.argv[1:])

2.main()函数

1def main(argv):
2    """
3    通过sys模块来识别参数
4    :return:
5    """
6    # 声明全局变量
7    global M, N
8    global MY_MAPS, OP
9    in_put = ""
10    out_put = ""
11    try:  # 获取参数并处理异常
12        opts, args = getopt.getopt(argv, "m:n:i:o:", ["help"])
13    except getopt.GetoptError:
14        print('Error: Sudoku.py -m -n -i -o')
15        sys.exit(2)
16    # 处理获取的参数
17    for opt, arg in opts:
18        if opt in "--help":  # 给予帮助提示
19            print('Error: Sudoku.py -m -n -i -o')
20            sys.exit()
21        elif opt in "-m":
22            M = int(arg)
23        elif opt in "-n":
24            N = int(arg)
25        elif opt in "-i":
26            in_put = arg
27        elif opt in "-o":
28            out_put = arg
29    with open(in_put, 'r', encoding='utf-8') as _fp_:  # 以读状态打开指定文件读取矩阵
30        _MYMAP_ = []
31        for line in _fp_.readlines():
32            if line != '\n':  # 用换行符分割矩阵
33                _MYMAP_.append(list(map(int, line.strip().split(" "))))
34            else:
35                MY_MAPS.append(_MYMAP_)
36                _MYMAP_ = []
37        MY_MAPS.append(_MYMAP_)  # MY_MAPS是集合了所有数据的三维数组
38
39    OP = open(out_put, 'w', encoding='utf-8')
40
41    for i in range(N):
42        if i > 0:
43            OP.write('\n')  # 分割矩阵
44        _DFS_(i, 0, 0)  # 递归求解
45    OP.close()
46

3.DFS()递归函数

1def _DFS_(_i_, _x_, _y_):
2    """
3    【DFS】深度优先搜索递归方式
4    :return:
5    """
6    # 声明引用全局变量
7    global M, MY_MAPS
8    if _x_ > M - 1:  # 完成条件
9        _MY_OTP_(_i_)  # 保存数值
10    elif MY_MAPS[_i_][_x_][_y_] != 0:  # 当前格子不可填
11        if _y_ == M - 1:  # 右边界换行
12            _DFS_(_i_, _x_ + 1, 0)
13        else:
14            _DFS_(_i_, _x_, _y_ + 1)  # 下一格
15    else:  # 当前格可填
16        for i in range(1, M + 1):
17            MY_MAPS[_i_][_x_][_y_] = i  # 试探填入数值
18            if judge(_i_, _x_, _y_):  # 判断其试探值的合法性,当判断函数返回值为1即合法
19                if _y_ == M - 1:  # 边界情况
20                    _DFS_(_i_, _x_ + 1, 0)
21                else:
22                    _DFS_(_i_, _x_, _y_ + 1)
23            # 回溯
24            MY_MAPS[_i_][_x_][_y_] = 0

4.judge()合法性判断函数

1def judge(_i_, _x_, _y_):
2    """
3    合法性判断
4    :return:
5    """
6    global M, MY_MAPS
7    # 行列不重复判断
8    for i in range(M):
9        if i != _x_ and MY_MAPS[_i_][_x_][_y_] == MY_MAPS[_i_][i][_y_]:
10            return 0
11        if i != _y_ and MY_MAPS[_i_][_x_][_y_] == MY_MAPS[_i_][_x_][i]:
12            return 0
13    # 区块重复判断
14    _x1_ = _y1_ = row = col = 0  # 块内坐标初始值
15    # 区块定位参考于https://github.com/zxw0621/demo/blob/master/20177596/src/sudoku.py#L42
16    # 这定位写的太好了
17    # 根据其阶数确定其模块规模以及所属模块
18    if M % 3 == 0:
19        row = 3
20        col = int(M / 3)
21    elif M % 2 == 0:
22        row = 2
23        col = int(M / 2)
24    _x1_ = int(_x_ // row * row)
25    _y1_ = int(_y_ // col * col)
26    # 遍历所属区块，检查其合法性
27    for i in range(_x1_, _x1_ + row):
28        for j in range(_y1_, _y1_ + col):
29            if _x_ != i and _y_ != j and MY_MAPS[_i_][_x_][_y_] == MY_MAPS[_i_][i][j]:
30                return 0
31    return 1

5.MY_OTP()数据储存函数

1def _MY_OTP_(_i_):
2    """
3    向文件内写入所得矩阵
4    :return:
5    """
6    global N, M, MY_MAPS, OP
7    # 遍历当前求解矩阵
8    for _x_ in range(M):
9        for _y_ in range(M):
10            OP.write(str(MY_MAPS[_i_][_x_][_y_]) + ' ')
11        OP.write('\n')  # 换行

6.异常处理

• 当参数输入异常时,输出提示帮助输入

  try: # 获取参数并处理异常 opts, args = getopt.getopt(argv, "m:n:i:o:", ["help"]) except getopt.GetoptError: print('Error: Sudoku.py -m -n -i -o') sys.exit(2)

• 当用户在命令行输入-help参数时，给予提示

  处理获取的参数

  1for opt, arg in opts:
  2    if opt in "--help":  # 给予帮助提示
  3        print('Error: Sudoku.py -m -n -i -o')
  4        sys.exit()
  5    elif opt in "-m":
  6        M = int(arg)
  7    elif opt in "-n":
  8        N = int(arg)
  9    elif opt in "-i":
  10        in_put = arg
  11    elif opt in "-o":
  12        out_put = arg
  

7.代码运行结果

命令行

输入文件

输出文件

至此程序宣布完成...

七、心路历程

记录

• 3月21日
  • 截至到12:00，目前仍然在研究代码实现思路（拖，就硬拖）
  • psp表格
  • 研究DFS递归函数
  • 设计功能模块
  • 查阅资料，实现命令行输入参数
  • 完成main()函数代码
  • 上传项目到GitHub，被网络折磨了半小时
  • 显然急于求成是愚蠢的，折磨了自己一晚上

<br/> <p style="width: 250px;height: 150px;margin: auto"><img src="https://img2020.cnblogs.com/blog/1952692/202003/1952692-20200323134524759-571132686.gif" alt=""></P> <br/>

• 3月22日
  • 截至到12:00，完成了博客的基本框架
  • 完成全部代码块
  • 完成流程图
  • 代码静态检测、性能分析、单元测试（折磨王三连折磨）
  • 代码优化，贼难受
  • 更新GitHub仓库（还好这波网络没炸）
  • 写博客
  • 终于完成了！！！芜湖~

——在本次任务中我深刻的认识到了不能闭门造车的道理，死钻牛角尖最后只会折磨自己，应该具有发散性的思维，充分利用网络资源查阅资料，从多个角度对问题进行分析。最终得出自己的解题思路。同时在工作学习时不能急于求成，这样反而会使得自己的效率下降，得不偿失。在遭遇挫折的时候不妨带着问题和其他人互相交流一番，或许问题会用迎刃而解。最后，事实证明写代码只占作业的10%，一系列附属操作把我给折磨的不轻...