【软件工程】个人项目 数独

发布于 2019-12-23  2133 次阅读


0x1 Github项目地址

SEproject

0x2 PSP表格

PSP2.1Personal Software Process Stages预估耗时(分钟)实际耗时(分钟)
Planning计划
· Estimate· 估计这个任务需要多少时间3020
Development开发
· Analysis· 需求分析(包括学习新技术)4060
· Design Spec· 生成设计文档9080
· Design Review· 设计复审(和同事审核设计文档)0
· Coding Standard· 代码规范(为目前的开发指定合适的规范)6035
· Design· 具体设计120120
· Coding· 具体编码1200720
· Code Review· 代码复审120180
· Test· 测试(自我测试,修改代码,提交修改)120
Reporting报告
· Test Report· 测试报告180
· Size Measurement· 计算工作量30
· Postmortem & Process Improvement Plan· 事后总结,并提出过程改进计划60
合计2050

0x3 思路描述

0. 项目结构

个人准备使用python完成开发任务,并将所实现的数独相关功能打包为一个sudoku包。编写主程序,调用包中具体的函数,完成功能实现。

1. 生成终局

  • 将满足条件的第一行分别右移 3、6、1、4、7、2、5、8列,可得余下的八行并以此组成一个终局。 对于每一个1~9的全排列,都可以通过这种方式来得到一个终局。还要求左上角的格子必须是学号后两位之和mod 9 + 1,故由此方法可得8!=40320种终局。 尚未达到题目要求。
  • 对于任何一个数独终局的1~3行,任意交换这三行的顺序,得到的仍然是一个合法的终局,4~6行和7~9行同理,列也同理。
  • 由于左上角不能动,所以只交换4~6行中的任意两行或者7~9行中的任意两行,这样在刚刚每种终局就可以变成3!×3!=36种终局,一共1451520种终局,达到了题目要求的1e6种终局数。

2. 求解数独

  • 求出每个数字为0的位置可以填的数。
  • 得出结果后优先填写约束条件多的(可填数字少的)0位置
  • 记录下填写过程,以备后续回溯
  • 填写过程中出现某处可填数据为空,则代表此前的某处填写有误。使用回溯法,回溯并更换数值
  • 直至最终所有数据填写完毕

0x4 设计实现过程

模块结构

模块内部函数调用

  • generator

盒图

函数关系

  • solver

函数关系

0x5 性能分析

对于生成数独的模块generator的测试

  • 模块时间分布
  • 函数时间分布

主要为python对象的建立与生成器的transform函数占用了较多资源

对于求解数独的模块solver的测试

  • 模块时间分布
  • 函数时间分布

主要为solver模块本身与其中的求解算法代码占用了较多资源

0x6 代码说明

0. 项目结构

.
├── libsudoku
│   ├── __init__.py
│   ├── generator.py
│   └── solver.py
└── sudoku.py

1. 生成终局

以下是sudoku中的generator的核心python实现:

def generate_list_3d(sum):

    num = 0

    for i_first_row in range(40320): # 对于行内8数字的全排列中的每一种,有:

        sudoku = [ [] for i in range(9)]
        init_row = list(next(row_iter))
        for i in range(9):
            row = init_row.copy()
            row.insert(0, '6')
            for j in range(shift[i]):
                row.insert(0,row.pop())
            sudoku[i] = row

        row_4_6_iter = itertools.permutations(sudoku[3:6], 3)
        for i_4_6_row in range(6): # 对于4-6行行间全排列中的每一种,有:

            temp_row = next(row_4_6_iter)
            for i in range(3, 6):
                sudoku[i] = temp_row[i-3]

            row_7_9_iter = itertools.permutations(sudoku[6:9], 3)
            for i_7_9_row in range(6): # 最后填写7-9行的一个全排列,完成一个数独终局

                temp_row = next(row_7_9_iter)
                for i in range(6, 9):
                    sudoku[i] = temp_row[i-6]

                sudoku_array.append(sudoku.copy())
                num += 1

                if num >= sum:
                    return sudoku_array
  • 使用python的迭代器生成了思路所述的两个全排列(行内数字全排列、4-6与7-9行行间全排列)
  • 使用多维列表作为存放与操作数独终局数据结构。

2. 求解数独

以下是sudoku中的solver的核心python实现:

def split_9_9(data): # 拆分9×9数独为9个3×3
    block_9_9 = numpy.zeros([3,3,3,3], dtype = int)
    for i in range(3):
        for j in range(3):
            block_9_9[i,j] = data[3*i:3*(i+1),3*j:3*(j+1)]
    return block_9_9

def get_num_set(data, block_9_9):
    picked_set = {}
    for i in range(9):
        for j in range(9):
            if data[i,j] == 0: # 以字典存储对应(i, j)处所有能填写的数字
                picked_set[str(i)+str(j)] = set(numpy.array(range(10))) - (set(data[i,:]) | set(data[:,j]) | set(block_9_9[i//3,j//3].ravel()))
    return picked_set

def solve_one(string): # 对一个数独谜题进行回溯法求解
    data = numpy.array(string.split(), dtype = int).reshape((9,9))
    insert_step = [] # 记录填写过程,使能回溯

    while True:
        picked_set = get_num_set(data, split_9_9(data))
        if len(picked_set) == 0: break
        pick_sort = sorted(picked_set.items(), key = lambda x:len(x[1]))
        item_min = pick_sort[0]
        key = item_min[0]
        value = list(item_min[1])
        insert_step.append((key, value))
        if len(value) != 0:
            data[int(key[0]), int(key[1])] = value[0]
        else:
            insert_step.pop()
            for i in range(len(insert_step)):
                huishuo = insert_step.pop()
                key = huishuo[0]
                insert_num = huishuo[1]
                if len(insert_num) == 1:
                    data[int(key[0]), int(key[1])] = 0
                else:
                    data[int(key[0]), int(key[1])] = insert_num[1]
                    insert_step.append((key, insert_num[1:]))
                    break

    out_str = '' #将数组转化为目标格式的字符串
    for i in data:
        for j in i:
            out_str += str(j)+' '
        out_str = out_str[0:-1]
        out_str += '\n'
    out_str += '\n'
    return out_str
  • 使用字典保存0处填写状态:键为对应坐标,值为可以填写的数字
  • 使用集合差集实现求解每个0处可以填写的数字:{1-9}的集合减去行中、列中、3×3中已出现的数字,余下的即为可以填的数