37.解数独

backtracking, set, https://leetcode.cn/problems/sudoku-solver/

编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 '.' 表示。

示例 1：

输入：board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

提示：

• board.length == 9
• board[i].length == 9
• board[i][j] 是一位数字或者 '.'
• 题目数据 保证 输入数独仅有一个解

这个代码超时了，如何优化

from typing import List

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        填充数独的解法（原地修改 board）
        """
        self.solve(board)

    def solve(self, board: List[List[str]]) -> bool:
        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':  # 发现空格
                    for num in map(str, range(1, 10)):  # 依次尝试填入 '1' - '9'
                        if self.isValid(board, i, j, num):  # 检查是否满足规则
                            board[i][j] = num
                            if self.solve(board):  # 递归求解
                                return True
                            board[i][j] = '.'  # 回溯
                    return False  # 没有可填的数，返回 False（触发回溯）
        return True  # 填完所有格子，返回 True

    def isValid(self, board: List[List[str]], row: int, col: int, num: str) -> bool:
        """
        检查在 (row, col) 位置填入 num 是否符合数独规则
        """
        block_x, block_y = (row // 3) * 3, (col // 3) * 3  # 计算 3x3 宫格的起始位置
        for i in range(9):
            if board[row][i] == num or board[i][col] == num:  # 检查行列
                return False
            if board[block_x + i // 3][block_y + i % 3] == num:  # 检查 3x3 宫格
                return False
        return True

如果超时了，可以优化 数独搜索的效率，主要思路如下：

优化思路

1. 使用哈希表（Set）存储已填入的数字
   • 维护 row_sets、col_sets 和 box_sets 记录已填入的数字，避免 isValid 的重复遍历。
2. 优先填充最少可选项的位置
   • 预处理所有空格，优先选择候选数最少的空格填充（最小剩余值原则 MRV）。

最小剩余值（Minimum Remaining Values, MRV）是一种用于解决约束满足问题（Constraint Satisfaction Problems, CSPs）的启发式策略。在CSP中，我们有一组变量，每个变量都必须被赋予一个值，同时还要满足一组约束条件，这些约束限制了哪些值可以合法地分配给变量。

MRV 的概念

MRV 启发式方法用于选择下一个要赋值的变量，具体来说，它会选择具有最少合法值（即剩余值最少）的变量进行赋值。这种策略背后的直觉是，如果一个变量的合法值较少，那么我们应该尽早处理它，因为如果不这样做，可能会导致后面的选择更加困难或者无解。

1. 回溯剪枝
   • 一旦发现无解，立即返回 False，减少不必要的搜索。

---

优化代码

from typing import List

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        解决数独问题，原地修改 board
        """
        self.rows = [set() for _ in range(9)]  # 每行已填数字集合
        self.cols = [set() for _ in range(9)]  # 每列已填数字集合
        self.boxes = [set() for _ in range(9)]  # 每个 3x3 宫格已填数字集合
        self.empty_cells = []  # 记录所有待填充的位置
        
        # 初始化状态
        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':
                    self.empty_cells.append((i, j))  # 记录空格
                else:
                    num = board[i][j]
                    self.rows[i].add(num)
                    self.cols[j].add(num)
                    self.boxes[(i // 3) * 3 + (j // 3)].add(num)

        # **排序空格：优先填充候选数最少的位置**
        self.empty_cells.sort(key=lambda pos: self.get_candidates_count(board, pos))
        
        self.solve(board, 0)  # 开始回溯填充

    def solve(self, board: List[List[str]], index: int) -> bool:
        """
        回溯填充数独
        """
        if index == len(self.empty_cells):
            return True  # 终止条件：所有空格填完
        
        row, col = self.empty_cells[index]
        box_index = (row // 3) * 3 + (col // 3)
        
        for num in map(str, range(1, 10)):  # 依次尝试 '1'-'9'
            if num not in self.rows[row] and num not in self.cols[col] and num not in self.boxes[box_index]:
                # 选择
                board[row][col] = num
                self.rows[row].add(num)
                self.cols[col].add(num)
                self.boxes[box_index].add(num)

                if self.solve(board, index + 1):  # 递归填充下一个
                    return True

                # 回溯
                board[row][col] = '.'
                self.rows[row].remove(num)
                self.cols[col].remove(num)
                self.boxes[box_index].remove(num)

        return False  # 触发回溯

    def get_candidates_count(self, board: List[List[str]], pos: tuple) -> int:
        """
        获取某个空格的可选数字数目（用于排序优化）
        """
        row, col = pos
        box_index = (row // 3) * 3 + (col // 3)
        used_numbers = self.rows[row] | self.cols[col] | self.boxes[box_index]
        return 9 - len(used_numbers)  # 可能的候选数

---

优化点

1. self.rows、self.cols、self.boxes

   • 直接记录已填数字，避免每次 isValid 进行 O(9) 遍历，查询复杂度变为 O(1)。

2. self.empty_cells.sort(key=lambda pos: self.get_candidates_count(board, pos))

   • 预排序所有空格，使得最少候选数的位置优先填充，大大减少回溯次数。

3. 回溯剪枝

   • 如果当前数字不满足约束，直接跳过，减少不必要的递归调用。

---

时间复杂度分析

• 由于 get_candidates_count 优化了搜索顺序，回溯的搜索空间大幅减少。
• 平均情况下复杂度从 O(9^n) 降低到 接近 O(9^m)，其中 m << n。