37. Sudoku Solver

题目

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

  1. Each of the digits 1-9 must occur exactly once in each row.
  2. Each of the digits 1-9 must occur exactly once in each column.
  3. Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

The '.' character indicates empty cells.

Example 1:

1
2
Input: 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"]]
Output: [["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"]]

Constraints:

  • board.length == 9
  • board[i].length == 9
  • board[i][j] is a digit or '.'.
  • It is guaranteed that the input Sudoku will have exactly one solution.

题目大意

编写一个程序通过填充空单元格来解决数独问题。数独解必须满足：每行、每列、每个 3x3 子网格中数字 1-9 恰好出现一次。

解题思路

方法一：基础回溯法

思路

使用回溯算法求解数独问题。回溯算法的核心思想是：尝试在当前空单元格填入一个数字，检查是否有效，如果有效则继续下一个单元格，否则撤销当前操作并尝试下一个数字。

复杂度分析

  • 时间复杂度：O(9^(空格数))，每个空格有 9 种选择。
  • 空间复杂度：O(1)，递归深度最大为空格数。

方法二：启发式搜索 + 最小堆（最优解）

方法来源：灵茶山艾府 - 数独？要玩题目就要玩透！
出处：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。2025年09月22日修改

思路

使用 MRV（Minimum Remaining Values）启发式搜索配合最小堆优化：

  1. 预记录空格位置：记录所有空格子的位置和每个格子的候选数字数量
  2. 最小堆优先：使用 heapq 实现最小堆，优先处理候选数最少的格子
  3. 动态更新：每次尝试后重新计算候选数，若失败则重新入堆

这种方法能在搜索树的早期就剪枝，大幅减少搜索空间，对于困难数独效果尤为显著。

复杂度分析

  • 时间复杂度：大幅剪枝后的 O(9^(空格数))，实际运行速度提升 100-1000 倍。
  • 空间复杂度：O(n)，n 为空格数，用于堆存储。

代码实现

方法一：基础回溯法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
from typing import List

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        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 c in '123456789':
                        if self.is_valid(board, i, j, c):
                            board[i][j] = c
                            if self.solve(board):
                                return True
                            board[i][j] = '.'
                    return False
        return True
    
    def is_valid(self, board: List[List[str]], row: int, col: int, c: str) -> bool:
        for i in range(9):
            if board[row][i] == c:
                return False
            if board[i][col] == c:
                return False
            if board[3 * (row // 3) + i // 3][3 * (col // 3) + i % 3] == c:
                return False
        return True

方法二：启发式搜索 + 最小堆（推荐）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
from typing import List
import heapq

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        # 数字映射
        digits = {str(i): i for i in range(1, 10)}
        
        # 记录每行、每列、每宫已填数字的集合
        row_set = [set() for _ in range(9)]
        col_set = [set() for _ in range(9)]
        sub_box_set = [[set() for _ in range(3)] for _ in range(3)]
        empty_pos = []

        # 初始化
        for i, row in enumerate(board):
            for j, b in enumerate(row):
                if b == '.':
                    empty_pos.append((i, j))
                else:
                    x = int(b)
                    row_set[i].add(x)
                    col_set[j].add(x)
                    sub_box_set[i // 3][j // 3].add(x)

        # 计算候选数
        def get_candidates(i, j):
            return 9 - len(row_set[i] | col_set[j] | sub_box_set[i // 3][j // 3])

        # 构建最小堆
        empty_heap = [(get_candidates(i, j), i, j) for i, j in empty_pos]
        heapq.heapify(empty_heap)

        # DFS
        def dfs() -> bool:
            if not empty_heap:
                return True

            _, i, j = heapq.heappop(empty_heap)
            candidates = 0

            for x in range(1, 10):
                if x in row_set[i] or x in col_set[j] or x in sub_box_set[i // 3][j // 3]:
                    continue

                # 尝试填入数字
                board[i][j] = str(x)
                row_set[i].add(x)
                col_set[j].add(x)
                sub_box_set[i // 3][j // 3].add(x)

                if dfs():
                    return True

                # 回溯
                row_set[i].remove(x)
                col_set[j].remove(x)
                sub_box_set[i // 3][j // 3].remove(x)
                candidates += 1

            # 重新入堆
            heapq.heappush(empty_heap, (candidates, i, j))
            return False

        dfs()