如何优化Python数独求解程序？解决RecursionError递归深度超限问题

我编写了一个Python数独求解程序，但效率极低，尝试次数过多时会触发错误：RecursionError: maximum recursion depth exceeded while calling a Python object，仅能偶尔运行极简单的数独。作为编程新手，我想知道如何提升程序效率？

以下是我的代码：

listekords = []

bo = [[0,2,1,0,0,3,0,4,0]
     ,[0,0,0,0,1,0,3,0,0]
     ,[0,0,3,4,0,5,0,0,0]
     ,[0,0,0,1,0,0,0,3,8]
     ,[0,8,9,0,0,0,4,7,0]
     ,[0,6,0,8,7,0,2,0,0]
     ,[9,0,0,0,0,0,0,0,4]
     ,[2,0,0,0,0,0,1,0,0]
     ,[0,0,0,5,8,2,0,0,0]]

def printso():
    for i in range(len(bo)):
        if i % 3 == 0 and i != 0:
            print("----------------")

        for j in range(len(bo[0])):
            if j != 8:
                print(bo[i][j], end="")
            else:
                print(bo[i][j])

            if (j+1)% 3 == 0 and j != 8:
                print("|", end="")

def passt(number, ky, kx):
    if number in bo[ky]:
        return False
    else:
        for z in range(len(bo)):
            if bo[z][kx] == number:
                return False

        for x in range(len(bo)):
                ky1 = ky // 3
                kx1 = kx // 3
                c = x // 3

                if kx1 == 0:
                    for y in bo[x][0:3:1]:
                        if y == number and c == ky1:
                            return False

                if kx1 == 1:
                    for y in bo[x][3:6:1]:
                        if y == number and c == ky1:
                            return False

                if kx1 == 2:
                    for y in bo[x][6:9:1]:
                        if y == number and c == ky1:
                            return False

                if x == 8:
                    return True

def isempty(i, j):
    return bo[i][j] == 0

def back():
    [i, j] = listekords.pop(len(listekords)-1)
    b = bo[i][j]
    print(b)
    bo[i][j] = 0
    printso()
    return b+1

def forward(b, i, j):
    print("vor")
    bo[i][j] = b
    listekords.append([i, j])
    printso()
    return b

def solve(d, b):
    for i in range(len(bo)):
        for j in range(len(bo[0])):
            if isempty(i, j):
                while not passt(b, i, j):
                    b += 1
                    print(b)

                if b > 9:
                    b = back()
                else:
                    forward(b, i, j)
                    b = 1
                print(d)
                solve(d+1, b)

solve(1, 1)
printso()

问题分析与优化方案 #

1. 递归逻辑混乱导致深度溢出

你的solve函数每次递归都会从头遍历整个棋盘，遇到第一个空单元格就处理，然后再次递归，这会导致同一单元格被反复处理，递归深度远超实际需要的81层，最终触发递归深度错误。标准回溯应该找到一个空单元格，尝试所有合法数字，递归求解，失败则回溯，而不是反复从头遍历。

2. passt函数效率低下

区块检查部分逻辑冗余，遍历整个9行再判断是否属于目标区块，完全可以直接计算目标3x3区块的起始坐标，只遍历9个单元格：

• 区块起始行：(ky // 3) * 3
• 区块起始列：(kx // 3) * 3
• 遍历从起始行到起始行+3，起始列到起始列+3的单元格即可

3. 全局变量与回溯逻辑复杂

用全局listekords记录坐标容易出错，且back/forward函数的打印操作会大幅拖慢速度，实际回溯只需要在递归失败时将单元格重置为0即可。

优化后的代码 #

bo = [[0,2,1,0,0,3,0,4,0]
     ,[0,0,0,0,1,0,3,0,0]
     ,[0,0,3,4,0,5,0,0,0]
     ,[0,0,0,1,0,0,0,3,8]
     ,[0,8,9,0,0,0,4,7,0]
     ,[0,6,0,8,7,0,2,0,0]
     ,[9,0,0,0,0,0,0,0,4]
     ,[2,0,0,0,0,0,1,0,0]
     ,[0,0,0,5,8,2,0,0,0]]

def print_board():
    for i in range(len(bo)):
        if i % 3 == 0 and i != 0:
            print("---------------------")
        for j in range(len(bo[0])):
            if j % 3 == 0 and j != 0:
                print("| ", end="")
            print(f"{bo[i][j]} ", end="")
        print()

def is_valid(number, row, col):
    # 检查行
    if number in bo[row]:
        return False
    # 检查列
    for r in range(9):
        if bo[r][col] == number:
            return False
    # 检查3x3区块
    block_row_start = (row // 3) * 3
    block_col_start = (col // 3) * 3
    for r in range(block_row_start, block_row_start + 3):
        for c in range(block_col_start, block_col_start + 3):
            if bo[r][c] == number:
                return False
    return True

def solve_sudoku():
    # 找到第一个空单元格
    for row in range(9):
        for col in range(9):
            if bo[row][col] == 0:
                # 尝试1-9的数字
                for num in range(1, 10):
                    if is_valid(num, row, col):
                        bo[row][col] = num
                        # 递归求解，如果成功直接返回True
                        if solve_sudoku():
                            return True
                        # 递归失败，回溯
                        bo[row][col] = 0
                # 所有数字都尝试过，无解，返回False
                return False
    # 所有单元格填满，求解成功
    return True

if solve_sudoku():
    print("求解完成：")
    print_board()
else:
    print("该数独无解")

优化点说明 #

• 递归逻辑简化：每次找到第一个空单元格，尝试所有合法数字，递归成功则立即返回，避免无效递归
• is_valid函数优化：区块检查直接定位目标3x3区域，减少遍历次数
• 去掉全局状态依赖：回溯逻辑直接在递归中处理，无需额外记录坐标的全局列表
• 移除冗余打印：仅在求解完成后打印结果，大幅提升运行速度

内容的提问来源于stack exchange，提问作者hansi