这个作业属于那个课程

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
https://www.cnblogs.com/ouyangpeng/p/8537616.html
https://blog.csdn.net/sunyanxiong123/article/details/76401590
https://github.com/zxw0621/demo/blob/master/20177596/src/sudoku.py

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

二、PSP表格

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

三、解题思路

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帮我整理一下...

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

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

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

2.代码性能优化

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

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

显然对于我来说这个图是天书

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

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

3.单元测试

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

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

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

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

• 测试代码编写

  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.导包和定义全局变量

# -*- coding: UTF-8 -*-
import sys
import getopt

# 全局变量
M = ""
N = ""
MY_MAPS = []
OP = ""

1.主函数

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

2.main()函数

def main(argv):
    """
    通过sys模块来识别参数
    :return:
    """
    # 声明全局变量
    global M, N
    global MY_MAPS, OP
    in_put = ""
    out_put = ""
    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)
    # 处理获取的参数
    for opt, arg in opts:
        if opt in "--help":  # 给予帮助提示
            print('Error: Sudoku.py -m -n -i -o')
            sys.exit()
        elif opt in "-m":
            M = int(arg)
        elif opt in "-n":
            N = int(arg)
        elif opt in "-i":
            in_put = arg
        elif opt in "-o":
            out_put = arg
    with open(in_put, 'r', encoding='utf-8') as _fp_:  # 以读状态打开指定文件读取矩阵
        _MYMAP_ = []
        for line in _fp_.readlines():
            if line != '\n':  # 用换行符分割矩阵
                _MYMAP_.append(list(map(int, line.strip().split(" "))))
            else:
                MY_MAPS.append(_MYMAP_)
                _MYMAP_ = []
        MY_MAPS.append(_MYMAP_)  # MY_MAPS是集合了所有数据的三维数组

    OP = open(out_put, 'w', encoding='utf-8')

    for i in range(N):
        if i > 0:
            OP.write('\n')  # 分割矩阵
        _DFS_(i, 0, 0)  # 递归求解
    OP.close()

3.DFS()递归函数

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

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

def judge(_i_, _x_, _y_):
    """
    合法性判断
    :return:
    """
    global M, MY_MAPS
    # 行列不重复判断
    for i in range(M):
        if i != _x_ and MY_MAPS[_i_][_x_][_y_] == MY_MAPS[_i_][i][_y_]:
            return 0
        if i != _y_ and MY_MAPS[_i_][_x_][_y_] == MY_MAPS[_i_][_x_][i]:
            return 0
    # 区块重复判断
    _x1_ = _y1_ = row = col = 0  # 块内坐标初始值
    # 区块定位参考于https://github.com/zxw0621/demo/blob/master/20177596/src/sudoku.py#L42
    # 这定位写的太好了
    # 根据其阶数确定其模块规模以及所属模块
    if M % 3 == 0:
        row = 3
        col = int(M / 3)
    elif M % 2 == 0:
        row = 2
        col = int(M / 2)
    _x1_ = int(_x_ // row * row)
    _y1_ = int(_y_ // col * col)
    # 遍历所属区块，检查其合法性
    for i in range(_x1_, _x1_ + row):
        for j in range(_y1_, _y1_ + col):
            if _x_ != i and _y_ != j and MY_MAPS[_i_][_x_][_y_] == MY_MAPS[_i_][i][j]:
                return 0
    return 1

5.MY_OTP()数据储存函数

def _MY_OTP_(_i_):
    """
    向文件内写入所得矩阵
    :return:
    """
    global N, M, MY_MAPS, OP
    # 遍历当前求解矩阵
    for _x_ in range(M):
        for _y_ in range(M):
            OP.write(str(MY_MAPS[_i_][_x_][_y_]) + ' ')
        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参数时，给予提示

  处理获取的参数

  for opt, arg in opts:
      if opt in "--help":  # 给予帮助提示
          print('Error: Sudoku.py -m -n -i -o')
          sys.exit()
      elif opt in "-m":
          M = int(arg)
      elif opt in "-n":
          N = int(arg)
      elif opt in "-i":
          in_put = arg
      elif opt in "-o":
          out_put = arg
  

7.代码运行结果

命令行

输入文件

输出文件

至此程序宣布完成...

七、心路历程

记录

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

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

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