一、题目分析

• 题目链接：LeetCode 37. 解数独
• 题目描述：在 9×9 的数独网格中，根据以下规则补全空白格（. 表示空白）：
  1. 每行包含 1-9 不重复数字；
  2. 每列包含 1-9 不重复数字；
  3. 每个 3×3 子九宫格包含 1-9 不重复数字。
• 难度：困难
• 核心考点：回溯法、约束验证、剪枝优化

二、解题思路

数独求解的核心是「回溯法」—— 这是解决约束满足类问题的经典框架，结合数独的强约束特性，通过「试填 - 验证 - 回溯」的逻辑高效找到解。

1. 核心思想

• 试填：对每个空白格，尝试填入 1-9 中符合约束的数字；
• 验证：通过提前记录的行、列、宫约束，快速判断数字是否合法；
• 回溯：若后续空白格无法填入合法数字，撤销当前选择，回到上一步尝试其他数字；
• 剪枝：优先处理候选数少的空白格，减少无效尝试，提升求解效率。

2. 关键优化策略

• 约束记录优化：用集合存储每行、每列、每宫的已使用数字，将合法性判断的时间复杂度从 O (9) 降到 O (1)；
• 剪枝优化：按候选数长度排序空白格，优先处理选择最少的格子（如只有 1 个候选数的格子），大幅减少回溯次数；
• 迭代式回溯：用栈模拟递归栈，避免递归深度限制，同时提升代码稳定性。

三、完整代码实现

from typing import List

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        # 初始化行、列、宫的约束记录（集合形式，O(1)查询）
        rowNums = [set(board[i][j] for j in range(len(board[0])) if board[i][j] != '.') for i in range(len(board))]
        colNums = [set(board[j][i] for j in range(len(board)) if board[j][i] != '.') for i in range(len(board[0]))]
        jggNums = [set() for _ in range(9)]
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] != '.':
                    jgg_idx = (i//3)*3 + j//3
                    jggNums[jgg_idx].add(board[i][j])

        # 收集空白格及初始候选数
        holes = []
        sRange9 = {str(i) for i in range(1, 10)}
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == '.':
                    jgg_idx = (i//3)*3 + j//3
                    candidates = list(sRange9 - rowNums[i] - colNums[j] - jggNums[jgg_idx])
                    holes.append([i, j, candidates])

        # 剪枝：优先处理候选数少的空白格
        holes.sort(key=lambda x: len(x[2]))

        # 迭代式回溯栈：(空白格索引, 已尝试的候选数索引)
        stack = [(0, 0)]

        while stack:
            hole_idx, l_idx = stack.pop()
            if hole_idx >= len(holes):
                return

            row, col, candidates = holes[hole_idx]

            # 回滚上一次的尝试
            if l_idx > 0:
                pre_num = candidates[l_idx - 1]
                rowNums[row].remove(pre_num)
                colNums[col].remove(pre_num)
                jggNums[(row//3)*3 + col//3].remove(pre_num)
                board[row][col] = '.'

            # 尝试当前候选数
            for i in range(l_idx, len(candidates)):
                current_num = candidates[i]
                jgg_idx = (row//3)*3 + col//3
                if (current_num not in rowNums[row] and
                    current_num not in colNums[col] and
                    current_num not in jggNums[jgg_idx]):
                    board[row][col] = current_num
                    rowNums[row].add(current_num)
                    colNums[col].add(current_num)
                    jggNums[jgg_idx].add(current_num)
                    stack.append((hole_idx, i + 1))
                    stack.append((hole_idx + 1, 0))
                    break