如何修改Python回溯法数独求解代码以统计所有解的数量

核心问题分析 #

你之前遇到的「解被重置为0」，本质是因为找到解后直接引用了原数独数组（可变对象），后续回溯操作会修改原数组内容，导致最终保存的解被覆盖。要实现多解收集，需要两个关键调整：

1. 找到完整解时保存数组的深拷贝，而非原数组引用
2. 找到解后不立即终止递归，继续回溯探索其他可能性

修改后的完整代码 #

假设你原代码有基础的is_valid合法性判断函数，以下是调整后的多解版本：

def find_all_solutions(board):
    solutions = []  # 存储所有解的副本

    def solve():
        # 遍历所有空白格（0代表空）
        for row in range(9):
            for col in range(9):
                if board[row][col] == 0:
                    # 尝试填入1-9的合法数字
                    for num in range(1, 10):
                        if is_valid(board, row, col, num):
                            board[row][col] = num
                            solve()  # 递归填充，找到解后不返回，继续探索
                            board[row][col] = 0  # 回溯，撤销当前填入的数字
                    return  # 当前格无合法数字，回溯至上一层
        
        # 找到完整解，保存深拷贝（避免后续回溯修改）
        solutions.append([row.copy() for row in board])
    
    solve()
    return solutions

# 辅助函数：判断当前位置填入num是否合法
def is_valid(board, row, col, num):
    # 检查当前行是否重复
    for i in range(9):
        if board[row][i] == num:
            return False
    # 检查当前列是否重复
    for i in range(9):
        if board[i][col] == num:
            return False
    # 检查3x3宫格是否重复
    box_row_start = (row // 3) * 3
    box_col_start = (col // 3) * 3
    for i in range(3):
        for j in range(3):
            if board[box_row_start + i][box_col_start + j] == num:
                return False
    return True

关键修改点说明 #

1. 移除终止递归的return逻辑：原代码找到一个解就return True终止递归，现在删除该逻辑，让递归在找到解后继续回溯，探索其他可能的数字组合
2. 保存解的深拷贝：用[row.copy() for row in board]创建数独的完整副本存入solutions，而非直接存原数组引用——这是解决「解被重置」的核心
3. 解的统计与输出：最终solutions列表的长度就是解的总数，遍历列表即可输出所有解

使用示例 #

# 测试用数独（0代表空白格）
test_board = [
    [5,3,0,0,7,0,0,0,0],
    [6,0,0,1,9,5,0,0,0],
    [0,9,8,0,0,0,0,6,0],
    [8,0,0,0,6,0,0,0,3],
    [4,0,0,8,0,3,0,0,1],
    [7,0,0,0,2,0,0,0,6],
    [0,6,0,0,0,0,2,8,0],
    [0,0,0,4,1,9,0,0,5],
    [0,0,0,0,8,0,0,7,9]
]

all_solutions = find_all_solutions(test_board)
print(f"共找到 {len(all_solutions)} 个解")
# 逐行输出所有解
for idx, sol in enumerate(all_solutions, 1):
    print(f"\n第 {idx} 个解：")
    for row in sol:
        print(row)

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