仅50行Python代码！数独求解！4秒！_【算法】数独解题——用python代码

可读性极高，直接上代码

递归求解

import numpy as np
from copy import deepcopy
def solve_recursion(pad, only_one_solve=True):
    '''递归求法'''
    pad = deepcopy(pad)
    pad = np.array(pad)
    pos = [-1, -1]  # 用来存放第一个未知数的位置
    possible = []  # 第一个未知数的位置可能的取值
    solves = []  # 解集
    if pad.max() > 9 or pad.min() < 0 or pad.shape != (9, 9):  # 异常保护
        raise ValueError("wtf with input value?")
    for y in range(9):  # 得到第一个未知数的位置
        if pos[0] != -1 and pos[1] != -1:  # 如果已经找到第一个未知数的位置
            break
        for x in range(9):
            if pad[y][x] == 0:
                pos = [x, y]
                break
    if pos[0] == -1 and pos[1] == -1:  # 第一个未知数的位置没找到，说明已经没有未知数了，已经解完
        print("find")
        return [pad]
    for k in range(1, 9 + 1):
        x = pos[0]
        y = pos[1]
        # 这一行内是否有k
        row = pad[y, :]
        if k in row:
            continue
        # 这一列内是否有k
        col = pad[:, x]
        if k in col:
            continue
        # 九宫格内是否有k
        box = pad[y - y % 3:y - y % 3 + 3, x - x % 3:x - x % 3 + 3]  # 切片出九宫格
        if k in box:
            continue
        possible.append(k)  # 这个位置为k时与当前已知情况不冲突
    if len(possible) == 0:  # 填什么都不满足当前的情况，无解
        return None
    for i in range(len(possible)):
        y = pos[1]
        x = pos[0]
        pad[y][x] = possible[i]  # 假设这个位置的数
        ret = solve_recursion(pad, only_one_solve=only_one_solve)  # 递归求解
        if ret is None:  # 无解
            pass
        elif isinstance(ret, list) and len(ret) == 0:  # 还没有解
            pass
        else:  # 解集
            if only_one_solve:
                return ret
            for j in range(len(ret)):
                solves.append(ret[j])
    return solves

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

传入参数：
pad，9x9二维list，pad[y][x]即x,y处对应的值，0表示未知，1-9对应1-9。
only_one_solve:True:求到一个解就直接中断求解，False:求完所有的解
返回值：
solves:解集list