如何修改Python递归数独求解函数，发现多解时立即终止

核心思路是通过追踪已找到的解的数量，一旦数量达到2，立刻终止所有递归分支，无需继续搜索更多解。具体实现步骤如下：

关键修改点 #

1. 使用可变对象（如列表）作为解计数器：Python中整数是不可变类型，递归函数内修改不会影响外层变量，而列表可以在递归中直接修改，实现跨递归层级的状态共享。
2. 递归入口提前判断：每次进入递归函数先检查计数器是否已达到2，若是则直接返回，终止当前分支。
3. 找到完整解时更新计数器：当数独被填满（找到一个解），计数器加1，若此时数量达到2，返回True触发上层递归终止。
4. 回溯过程加入检查：在每次回溯后的循环中，若计数器已达2，立刻终止循环并返回。

修改后的代码示例 #

假设你原有的递归求解函数包含find_empty（寻找空白格）和valid（验证数字合法性）函数，修改后的solve函数如下：

def solve(board, solution_count):
    # 提前判断：已找到2个解，直接终止当前递归分支
    if solution_count[0] >= 2:
        return False

    find = find_empty(board)
    if not find:
        # 找到一个完整解，计数器加1
        solution_count[0] += 1
        # 若已找到2个解，返回True触发上层终止
        return solution_count[0] >= 2
    else:
        row, col = find

    for num in range(1, 10):
        if valid(board, num, (row, col)):
            board[row][col] = num

            # 递归调用，传递计数器
            if solve(board, solution_count):
                return True

            # 回溯，恢复空白格
            board[row][col] = 0

            # 回溯后检查：若已找到2个解，立刻终止循环
            if solution_count[0] >= 2:
                return True

    return False

调用方式 #

# 初始化计数器（用列表实现可变状态）
solution_count = [0]
# 传入你的数独棋盘和计数器
solve(your_sudoku_board, solution_count)

# 根据计数器结果输出判断
if solution_count[0] > 1:
    print("该数独存在多个解")
else:
    print("该数独仅有一个解")

原理说明 #

• 计数器采用列表[0]而非单独整数，是为了让递归函数能直接修改外层的计数值，避免因不可变类型导致的状态隔离。
• 每次递归分支启动前的检查，能快速终止不必要的搜索；回溯后的检查则确保在找到第二个解的瞬间，立刻停止所有后续循环和递归，最大程度节省计算资源。

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