LeetCode 题解工作台
解数独
编写一个程序，通过填充空格来解决数独问题。 数独的解法需 遵循如下规则 ： 数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图） 数独部分空格内已填入了数字，空白格用 '.' 表示。 示例 1： …
4
题型
6
代码语言
3
相关题
当前训练重点
困难 · 数组·哈希·扫描
答案摘要
我们用数组 , , 分别记录每一行、每一列、每个 3x3 宫格中数字是否出现过。如果数字 在第 行、第 列、第 个 3x3 宫格中出现过，那么 , , 都为 。 我们遍历 中的每一个空格，枚举它可以填入的数字 ，如果 在当前行、当前列、当前 3x3 宫格中没有出现过，那么我们就可以尝试填入数字 ，并继续搜索下一个空格。如果搜索到最后，所有空格填充完毕，那么就说明找到了一个可行解。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规则：
- 数字
1-9在每一行只能出现一次。 - 数字
1-9在每一列只能出现一次。 - 数字
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 == 9board[i].length == 9board[i][j]是一位数字或者'.'- 题目数据 保证 输入数独仅有一个解
解题思路
方法一：回溯
我们用数组 , , 分别记录每一行、每一列、每个 3x3 宫格中数字是否出现过。如果数字 在第 行、第 列、第 个 3x3 宫格中出现过，那么 , , 都为 。
我们遍历 中的每一个空格，枚举它可以填入的数字 ，如果 在当前行、当前列、当前 3x3 宫格中没有出现过，那么我们就可以尝试填入数字 ，并继续搜索下一个空格。如果搜索到最后，所有空格填充完毕，那么就说明找到了一个可行解。
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
def dfs(k):
nonlocal ok
if k == len(t):
ok = True
return
i, j = t[k]
for v in range(9):
if row[i][v] == col[j][v] == block[i // 3][j // 3][v] == False:
row[i][v] = col[j][v] = block[i // 3][j // 3][v] = True
board[i][j] = str(v + 1)
dfs(k + 1)
row[i][v] = col[j][v] = block[i // 3][j // 3][v] = False
if ok:
return
row = [[False] * 9 for _ in range(9)]
col = [[False] * 9 for _ in range(9)]
block = [[[False] * 9 for _ in range(3)] for _ in range(3)]
t = []
ok = False
for i in range(9):
for j in range(9):
if board[i][j] == '.':
t.append((i, j))
else:
v = int(board[i][j]) - 1
row[i][v] = col[j][v] = block[i // 3][j // 3][v] = True
dfs(0)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Do you understand how backtracking helps with solving constraint satisfaction problems like Sudoku?
- question_mark
Can you explain how using hash sets optimizes the time complexity of the backtracking approach?
- question_mark
Will you be able to handle edge cases, such as when the Sudoku grid is almost solved but still contains a few empty cells?
常见陷阱
外企场景- error
Not properly updating hash sets after placing numbers, which could lead to incorrect checks for subsequent placements.
- error
Overcomplicating the backtracking approach by not pruning branches early enough, leading to unnecessary recursion.
- error
Failing to correctly handle the constraints of the 3x3 subgrids, which could result in invalid Sudoku solutions.
进阶变体
外企场景- arrow_right_alt
Solve a Sudoku puzzle where the board contains multiple solutions (not guaranteed to have one solution).
- arrow_right_alt
Implement a Sudoku solver using a constraint propagation technique like AC-3 or similar.
- arrow_right_alt
Create a Sudoku solver that generates random Sudoku puzzles while ensuring a unique solution.