如何优化数独求解器性能？递归实现性能提升求助

原代码的性能瓶颈并非递归本身，而是填充策略低效、候选值重复计算这两个核心问题，以下是针对性的优化方案：

核心优化点 #

1. 采用「最少剩余值（MRV）」启发式填充 #

原代码每次从左到右、从上到下找第一个空单元格填充，很容易提前走进无解分支，导致大量无效回溯。优先选择候选值最少的空单元格填充，能大幅减少回溯次数，这是数独求解器性能提升的关键。

2. 预维护行列块的已用数字集合 #

原代码每次计算候选值都要遍历整行、整列、整个3x3块，重复计算开销极大。改用三个数组分别记录每行、每列、每个3x3块的已用数字，填充/回溯时实时更新，候选值计算直接用全集减已用集合，效率提升明显。

3. 避免冗余的集合转换与列表操作 #

原代码中row_values + col_values + box_values的拼接和集合转换是不必要的开销，用预维护的已用集合直接计算差集，能节省大量时间。

优化后的代码 #

def solve_sudoku(board):
    # 初始化行、列、3x3块的已用数字集合
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]
    empty_cells = []

    # 初始化已用数字集合和空单元格列表
    for r in range(9):
        for c in range(9):
            val = board[r][c]
            if val != 0:
                rows[r].add(val)
                cols[c].add(val)
                # 计算当前单元格所属的3x3块索引
                box_idx = (r // 3) * 3 + (c // 3)
                boxes[box_idx].add(val)
            else:
                empty_cells.append((r, c))

    def backtrack():
        if not empty_cells:
            return True
        
        # 找到候选值最少的空单元格（MRV启发式）
        min_options = 10
        target_cell = None
        for (r, c) in empty_cells:
            box_idx = (r // 3) * 3 + (c // 3)
            used = rows[r].union(cols[c]).union(boxes[box_idx])
            options = 9 - len(used)
            if options < min_options:
                min_options = options
                target_cell = (r, c)
                if min_options == 1:  # 提前终止，找到唯一候选的单元格
                    break
        
        r, c = target_cell
        box_idx = (r // 3) * 3 + (c // 3)
        used = rows[r].union(cols[c]).union(boxes[box_idx])
        candidates = set(range(1, 10)) - used

        for num in candidates:
            # 填充数字并更新已用集合
            board[r][c] = num
            rows[r].add(num)
            cols[c].add(num)
            boxes[box_idx].add(num)
            empty_cells.remove((r, c))

            if backtrack():
                return True
            
            # 回溯：恢复状态
            board[r][c] = 0
            rows[r].remove(num)
            cols[c].remove(num)
            boxes[box_idx].remove(num)
            empty_cells.append((r, c))
        
        return False

    backtrack()
    return board

# 测试用例
problem = [
    [9, 0, 0, 0, 8, 0, 0, 0, 1],
    [0, 0, 0, 4, 0, 6, 0, 0, 0],
    [0, 0, 5, 0, 7, 0, 3, 0, 0],
    [0, 6, 0, 0, 0, 0, 0, 4, 0],
    [4, 0, 1, 0, 6, 0, 5, 0, 8],
    [0, 9, 0, 0, 0, 0, 0, 2, 0],
    [0, 0, 7, 0, 3, 0, 2, 0, 0],
    [0, 0, 0, 7, 0, 5, 0, 0, 0],
    [1, 0, 0, 0, 4, 0, 0, 0, 7]
]

print(solve_sudoku(problem))

额外优化建议 #

• 如果追求极致性能，可以加入「唯一候选数」「唯一位置」等约束传播规则，在回溯前先填充那些只有唯一解的单元格，进一步减少回溯次数。
• 避免在empty_cells中频繁调用remove和append，可以改用索引标记的方式（比如用一个列表记录空单元格，用指针跟踪当前处理位置），不过对于9x9数独来说，当前方案的开销已经可以忽略。

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