Sudoku_Study_daily

2019/12/16

今天开始启动了软件工程大作业的工作，大概做了如下：

• 创建一个github仓库Soduku(这里貌似打错了，本来是Sudoku，但由于已经交给老师的仓库链接是之前的那个，也就没有进行更改了)

• 预计需消耗时间，撰写PSP表格部分内容

• 需求分析

• 生成终局

  • 在命令行中使用-c参数加数字N(1≤N≤1000000)控制生成数独终局的数量

    sudoku.exe -c N

  • 将生成的数独终局用一个文本文件(假设名字叫sudoku.txt)的形式保存起来，每次生成的txt文件需要覆盖上次生成的txt文件，文件内的格式如下，数与数之间由空格分开，终局与终局之间空一行，行末无空格

  • 程序在处理命令行参数时，不仅能处理格式正确的参数，还能处理各种异常的情况，如：

    sudoku.exe -c abc

  • 在生成数独矩阵时，左上角的第一个数为：(学号后两位相加)%9+1。

• 求解数独

  • 在命令行中使用-s参数加文件名的形式求解数独，并将结果输出至文件，如：

    sudoku.exe -s absolute_path_of_puzzlefile

    程序将从路径中读取数独题目，并将数独题目的一个可行解输出至sudoku.exe同目录的sudoku.txt，要求与生成终局相同。

  • 数独题目格式：其中0代表空格，题目与题目之间空一行，行末无空格，最后一个数独题目后无空行。

  • 数独题目个数N(1≤N≤1000000)，保证文件中的数独格式正确。

  • 其他要求

    • 需要对代码进行一定的注释。
    • 要求程序在60s内给出结果。

• 搭建项目内容的博客框架，参考如下网站

  https://blog.csdn.net/Pan_Quixote/article/details/84678996

• 收集数独生成终局的资料，大概查阅如下网站：

  https://www.cnblogs.com/BIT1120161931/p/8618878.html
  https://blog.csdn.net/Pan_Quixote/article/details/84678996

  ps:此时没有在创建博客，所以相关内容暂且写到本地文件上

2019/12/19

• 选取一个合适的算法——数列法，并分析其可行性

• 使用python语言完成编写

• 思路大致如下：

  # sudoku_generate.py
  # 先确定左上角的数字为5
  # 由所述算法可知 对每一行的一位操作变换是基于0,3,6 ,1,4,7, 2,5,8(此处首位应该保持不变为0)
  # 对于每一种全排列都有30种终局
  # 由于每种排列需要生成30种终局，提前将变化方式记录如下 
  move_way = (
      '''
      这里省略30变换方式，可见github仓库源代码文件
      '''
  )
  '''
  将生成终局的类命名为create_sudoku,对其进行包装
  '''
  class create_sudoku:
      def __init__(self, num):
          '''
          初始化各种类
          '''
      def create_sudoku(self):
           '''
           1. 得到一个全排列
           2. 通过全排列进行30种变换
           3. 再得到全排列，返回1，直到创建了足够数量数独
           '''
      
      def nextPermutation(self, nums):
          '''
          通过回溯法，求解全排列
          '''
      def write2file(self):
          '''
          将数独写入文件
          '''

• 对其进行单元测试

2019/12/20

• 建立主控函数sudoku.py，代码详情见github仓库

  #coding=utf-8
  #owner: IFpop
  #time: 2019/12/20
  
  import sudoku_generate
  from copy import deepcopy
  import sys
  import time
  
  def main():
      try:
          cmd = sys.argv[1]
          print("cmd:"+cmd)
          # 如果是-c的话。就执行create
          if cmd[1] == 'c':
              '''
              生成数独
              '''
          elif cmd[1] == 's':
              '''
              解数独
              '''
  
      except ValueError:
          print("please input correct number")
      except IOError:
          print("Error: Not find or open failed!")
  
  main()

• 使用命令对其进行测试

  python suoku.py -c 1000000
  
  running time is 30.9375

  效果并不是特别理想。此时没有进行性能分析，之后和解数独一起进行分析

2019/12/21

• 创建一个博客

• 将之前所写的本地内容填到其中

• 编写解题程序(一部分)

  • 处理文本读取部分以及时间输出

    # 打开文件
            with open(filepath, 'r') as f:
                line = f.readline()
                num = 0  #记录当前是否是第九行
                cur = 0  #记录当前个数
                temp = []
                while line:
                    if(line[0] != '\n' and num != 9):
                        line = [int(i) for i in line if str.isdigit(i)]
                        temp.append(deepcopy(line))
                        num += 1
                        line = f.readline()
                    # 已经收集了一个数独
                    elif num == 9 or line[0] == '\n':
                        line = f.readline()
                        num = 0
                        print(cur)
                        cur += 1
                        self.current_sudoku = SudoKu(temp)
                        start = time.time()
                        self.sudo_solve()
                        self.current_sudoku.value = self.current_sudoku.value.tolist()
                        ans.append(self.current_sudoku.value)
                        end = time.time()
                        print("time is %.4f" % (end-start))
                        temp = []
            print(cur)
            # 最后一个
            self.current_sudoku = SudoKu(temp)  
            start = time.time()
            self.sudo_solve()
            self.current_sudoku.value = self.current_sudoku.value.tolist()
            ans.append(self.current_sudoku.value)
            end = time.time()
            print("time is %.4f" % (end-start))

2019/12/22

• 完善解题功能
• 更新博客

2019/12/26

• 为解数独程序添加注释

• 上传测试用例

• 规范代码格式

• 进行性能测试

  • 使用VS进行性能分析，首先是对生成终局进行性能分析

    • 模块时间分布

      使用【调试】中的启动python分析得到

      

      由图中分析可以知道占用时间主要集中于__init__和create。

    • 函数时间分布

      

      时间消耗主要集中于write2file函数以及get_sudoku函数中。

    • 时间分布图

      #为了能够更加直观的看出那个模块以及函数的时间消耗，增加了利用cprofile(分析时间）以及gprof2dot（可视化）
      #参考文献进行了性能分析: https://zhuanlan.zhihu.com/p/24495603

      

    此处可以看出replace切割相对于其他比较耗时。

    • 原因分析及解决方案

      ​ 首先是write2file以及get_sudoku函数，最开始的思路是得到一个终局写入一次，但事实证明效率极低，目前采用的策略是将全部的数独存到一个list变量perm中，最后集中写入。而replace比较耗时，这是因为python本身的特性决定的，python是一种解释性语言，前期的编译是将 Python 代码编译成解释器可以理解的中间代码，解释器再将中间代码翻译成CPU可以理解的指令,相比于 AOT(提前编译型语言，比如C)直接编译成机器码，肯定是慢的。那么要怎样才能使用python到达c的速度呢?由此我决定使用cython(一种C语言与python的结合体)写数独过程。学习过程参看博客。

      ​ 另外，生成全排列的函数nextPermutation，采取的措施是每次遍历完30个move_way之后才会获取下一个全排列，大大增加了该函数的调用次数，也浪费了时间。由此，我之后采用先将所有的全排列生成然后存储起来，之后直接访问即可。

      ​ 最后就是文件写入函数也会有占用大量时间，目前采用的策略是对于每一个数独，逐个写入，这样会多次调用write函数，所以最终的方案是建立一个缓存区，将数独以字符串形式存入，最后一起写入。结合cython，可以使用更快的fputs进行一次性写入。

• 解数独性能及优化

  • 函数时间分布

    使用【调试】中的启动python分析得到

    

  • 时间分布图

    

    从上面的图中可以看出来，guess函数耗时过多，其次就是排除候选的三种算法耗时也比较多。

  • 原因分析

    • python语言本身的原因
    • 没有将其变为字符串一次写入，在write上耗时过多

  • 解决方案

    • 建立一个缓冲区，优化写入过程
    • 优化一下排除候选的算法

2020/1/1

• 使用cython

  将sudoku_generate.py用cython进行 编程,建立缓冲区

  最终结果：

语言	生成1000000个终局所耗时间
python(最开始)	30.9375
c/c++	2.4605
cython	2.6758

• 更新博客

2020/1/2

• GUI设计

  • GUI环境搭建

    # Requirement
    pyqt5
    pyqt5-tools
    opencv-python

  • 安装完上述软件后,点击[工具]-–>[外部工具]-–>[添加]

    分别添加pyqt5Design.exe,pyuic5.exe,pyrcc5.exe

    

    

    

2020/1/3

• 界面设计思路(需求拟定)

  1. 可以动态显示当前时间，年月日
  2. 可以选择难度Level，分为Easy、Medium、Hard
  3. 可以显示当前所选难度
  4. 可以显示剩余的空格数量，并在数独界面上将空格置为绿色(便于观察)
  5. 设有start的按钮，用于游戏开始以及重开
  6. 设有next，代表下一步，也代表提示功能，当点击下一步时，可以帮你随机填入一个点
  7. 设有last，代表上一步，可以恢复上一状态
  8. 设置图片，标识此前状态，有未开始游戏，开始游戏，游戏失败，游戏成功
  9. 对于每一个输入，都要对其进行判断
     • 如果是行发生问题，将此格标红
     • 如果是列发生问题，将此格标红
     • 如果是九宫格发生问题，将此格标红
     • 否则，就正确进行下一步

• 使用QtDesign画出我想要的界面，大概如下

  

• 然后使用PyUIC5工具直接将之前QtDesign所保存的.ui文件转换为.py文件

• GUI代码编写

  在写这部分内容过程中，是将之间的solve以及generate作为接口进行调用，但是由于之前使用cython，发现并不能调用模块下的变量，所以暂且使用之间最开始的python版本进行编写这部分内容，随后进行对应优化。

  • 新建一个sudoku.py，在GUIBIN文件夹中新建一个，对GUI进行调用,伪代码如下：

    # sudoku.py 界面启动主程序
    '''
    栈结构，用于存储所走的步骤
    '''
    class MyStack(object):
        def __init__(self):
        # 创建一个栈
        def create_stack(self):
        # 栈中添加值
        def push(self, value):
        #返回栈顶元素值
        def peek(self):
        # 删除栈顶元素
        def pop(self):
        # 返回栈是否为空
        def is_empty(self):
        def print_all(self):
    '''
    程序主窗口界面
    '''
    class Face(QMainWindow):
        def __init__(self, parent=None):
            #游戏初始等级为1
            '''
            1 —— EASY
            2 —— MEDIUM
            3 —— HARD
            '''
            # 使用堆栈实现上一步操作
            self.last = MyStack()
            # 启动方式
            super(Face, self).__init__(parent)
            #
            self.ui = Ui_MainWindow()
            self.ui.setupUi(self)
            self.setFixedSize(self.width(), self.height())
    
            # 分别设置开始，上一步，下一步文本
            self.ui.start.setText("START")
            self.ui.Done.setText("DONE")
            self.ui.Last.setText("LAST")
            self.ui.Next.setText("NEXT")
            # 初始选择难度为Easy
            self.ui.Level_state.setText("EASY")
            self.ui.Level_state.setReadOnly(True)
            self.ui.Level_state.setStyleSheet(
                "background-color: transparent;")
            self.ui.surplus.setText(str(self.hoels))
            self.ui.surplus.setReadOnly(True)
            self.ui.surplus.setStyleSheet(
                "background-color: transparent;")
            self.setWindowTitle("Sudoku Game")
            # 设置当前时间
            self.GetCurtime()
            # 游戏4种状态 
            '''
            0 —— 尚未开始  happy
            1 —— 开始游戏  come on
            2 —— 成功解出数独 
            3 —— 失败
            '''
            # 初始为0
            self.Put_pic(0)
            
            # 链接按钮功能
            self.ui.start.clicked.connect(self.start_game)
            self.ui.Done.clicked.connect(self.Game_Done)
            self.ui.Last.clicked.connect(self.Recover)
            self.ui.Next.clicked.connect(self.Next_step)
    
            # 菜单功能
            self.ui.actionEasy.triggered.connect(self.change_easy)
            self.ui.actionMedium.triggered.connect(self.change_medium)
            self.ui.actionHard.triggered.connect(self.change_hard)
       '''
       其他函数，实现过程请前往github仓库查看
       '''
            
    if __name__ == "__main__":
            app = QApplication(sys.argv)
            myapp = Face()
            myapp.show()
            sys.exit(app.exec_())

  • 新建一个Get_one_sudoku.py，生成一个待解决的数独,伪代码如下：

    #Get_one_sudoku.py
    #owner: IFpop
    #time: 2020/1/3

  • 其中需要调用生成终局sudoku_generate.py以及sudo_solve.py中模块，直接以此为接口进行引用即可。

• GUI目前完成了显示功能，还有check_value，即检测所填数独是否正确，这部分并没有完成，这部分可能会等最近考试完成之后再进行。

• 中期汇编ppt，进行了撰写，然后发到老师邮箱。

• 按老师要求，将博客细分为一定时间所作的事情，并实时更新。

2020/1/7

• 完成GUI部分代码编写

• 最终效果如下：

  • 初始界面

    

  • 开始游戏

    

  • 点击下一步进行补全

    

  • 使用上一步进行恢复

    

  • 在未完成的情况下，点击DONE

    

  • 完成一局游戏后，如果正确，将会出现如下结果

    

• 更新个人博客

2020/1/18

• 增添单元测试以及覆盖率测试

  • 具体见Sudoku

• 找人测试界面，对出现的错误进行修改

  在测试过程中，当游戏尚未开始的时候，点击Last以及点击Next的时候，会出现报错

  原因分析及解决方案：

  • 没有对当前状态进行判断，设置一个state变量，标志游戏是否已经开始
  • 若是已经开始，一切正常
  • 若是没有开始，则提示"You haven't start yet"

• 将python项目打包成exe文件

  • 安装pyinstaller

    python -m pip install pyinstaller

  • 没有界面的数独

    将文件全部放到一个大的文件夹中，先生成.spec文件

    pyi-makespec sudoku.py

    得到sudoku.spec，对其进行如下更改:

    # sudoku.spec
    # -*- mode: python ; coding: utf-8 -*-
    
    block_cipher = None
    a = Analysis(['sudoku.py','sudo_solve.py'],
                 pathex=['C:\\Users\\96552\\Desktop\\test'],
                 binaries=[],
                 datas=[],
                 hiddenimports=[],
                 hookspath=[],
                 runtime_hooks=[],
                 excludes=[],
                 win_no_prefer_redirects=False,
                 win_private_assemblies=False,
                 cipher=block_cipher,
                 noarchive=False)
    pyz = PYZ(a.pure, a.zipped_data,
                 cipher=block_cipher)
    exe = EXE(pyz,
              a.scripts,
              [],
              exclude_binaries=True,
              name='sudoku',
              debug=False,
              bootloader_ignore_signals=False,
              strip=False,
              upx=True,
              console=True )
    coll = COLLECT(exe,
                   a.binaries,
                   a.zipfiles,
                   a.datas,
                   strip=False,
                   upx=True,
                   upx_exclude=[],
                   name='sudoku')

  • 有界面的数独

    将文件全部放到一个大的文件夹中，先生成.spec文件

    pyi-makespec sudokuGui.py

    得到sudokuGui.spec，对其进行如下更改:

    # sudokuGui.spec
    # -*- mode: python ; coding: utf-8 -*-
    block_cipher = None
    a = Analysis(['sudokuGui.py','Get_one_Sudoku.py','sudo_solve.py','sudoku_faceForm.py','sudoku_generate.py'], # 这里添加依赖文件
                 pathex=['C:\\Users\\96552\\Desktop\\test'],
                 binaries=[],
                 datas=[('C:\\Users\\96552\\Desktop\\test\\Pic','Pic')],  # 这里添加非python文件
                 hiddenimports=[],
                 hookspath=[],
                 runtime_hooks=[],
                 excludes=[],
                 win_no_prefer_redirects=False,
                 win_private_assemblies=False,
                 cipher=block_cipher,
                 noarchive=False)
    pyz = PYZ(a.pure, a.zipped_data,
                 cipher=block_cipher)
    exe = EXE(pyz,
              a.scripts,
              [],
              exclude_binaries=True,
              name='sudokuGui',
              debug=False,
              bootloader_ignore_signals=False,
              strip=False,
              upx=True,
              console=True )
    coll = COLLECT(exe,
                   a.binaries,
                   a.zipfiles,
                   a.datas,
                   strip=False,
                   upx=True,
                   upx_exclude=[],
                   name='sudokuGui')

• 完善博客

• 在github对应仓库添加使用说明