LeetCode【0037】解数独

1 中文题目

编写一个程序，通过填充空格来解决数独问题。数独的解法需 遵循如下规则：

• 数字 1-9 在每一行只能出现一次。
• 数字 1-9 在每一列只能出现一次。
• 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
• 数独部分空格内已填入了数字，空白格用 ‘.’ 表示。

示例：

输入：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] 是一位数字或者 ‘.’
• 题目数据 保证 输入数独仅有一个解

---

2 求解方法：递归+回溯法

2.1 方法思路

方法核心

使用回溯算法解决数独问题，使用三个二维数组记录数字使用情况，采用逐个位置填写的策略，通过位置编号简化行列索引计算。

实现步骤

（1）初始化阶段：

• 创建三个二维数组记录每行、每列和每个3x3方块中数字的使用情况
• 遍历数独板，标记已有数字的使用情况
• 将问题转化为填写空位的问题

（2）回溯过程：

• 使用位置编号（0-80）表示当前填写位置
• 通过整除和取余计算行列索引
• 如果当前位置已有数字，继续下一个位置。否则尝试填入1-9的数字

（3）验证过程：

• 检查当前数字是否可以在行中使用，检查当前数字是否可以在列中使用，检查当前数字是否可以在3x3方块中使用
• 所有检查都通过才能填入数字

方法示例

输入数独板示例：
[["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"]
]执行过程示例（以填写第一个空位为例）：1. 定位第一个空位：- 位置 (0,2)- box_index = (0 // 3) * 3 + 2 // 3 = 02. 尝试填入数字：- 检查数字1：已在同行/列/方块使用- 检查数字2：已在同行/列/方块使用- 检查数字4：可以使用- 填入数字4并继续递归3. 如果后续填写失败：- 回溯到当前位置- 清除数字4- 尝试下一个可能的数字4. 递归和回溯过程继续，直到找到完整解答

2.2 Python代码

class Solution:def solveSudoku(self, board: List[List[str]]) -> None:"""Do not return anything, modify board in-place instead."""# 初始化三个二维数组，分别记录行、列和3x3方块中数字的使用情况rows = [[False] * 9 for _ in range(9)]cols = [[False] * 9 for _ in range(9)]boxes = [[False] * 9 for _ in range(9)]# 遍历整个数独板，记录已有数字的使用情况for i in range(9):for j in range(9):if board[i][j] != '.':num = int(board[i][j]) - 1  # 转换为0-8的索引box_index = (i // 3) * 3 + j // 3rows[i][num] = Truecols[j][num] = Trueboxes[box_index][num] = Truedef backtrack(pos: int) -> bool:# 如果已经填完所有位置，返回Trueif pos == 81:return True# 计算当前位置的行列索引row, col = pos // 9, pos % 9# 如果当前位置已有数字，尝试填写下一个位置if board[row][col] != '.':return backtrack(pos + 1)# 计算当前位置所在的3x3方块索引box_index = (row // 3) * 3 + col // 3# 尝试填入1-9的数字for num in range(9):# 检查当前数字是否可以填入if not (rows[row][num] or cols[col][num] or boxes[box_index][num]):# 标记数字使用情况rows[row][num] = cols[col][num] = boxes[box_index][num] = Trueboard[row][col] = str(num + 1)# 递归尝试填写下一个位置if backtrack(pos + 1):return True# 回溯：恢复标记和数独板rows[row][num] = cols[col][num] = boxes[box_index][num] = Falseboard[row][col] = '.'# 当前位置无法填入任何数字return False# 从第一个位置开始解数独backtrack(0)

2.3 复杂度分析

• 时间复杂度：O(9^m)，m是空格的数量
  • 每个空格最多尝试9个数字
  • 实际运行时间因剪枝而大大减少
• 空间复杂度：O(m)，m是空格的数量（递归栈深度）
  • 三个固定大小的二维数组（81个布尔值）

---

3 题目总结

题目难度：困难
数据结构：矩阵
应用算法：回溯、递归