解数独
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
编写一个程序，通过填充空格来解决数独问题。
数独的解法需遵循如下规则：
- 数字
1-9在每一行只能出现一次。 - 数字
1-9在每一列只能出现一次。 - 数字
1-9在每一个以粗实线分隔的3×3宫内只能出现一次。
数独部分空格内已填入了数字，空白格用 '.' 表示。题目数据保证输入数独仅有一个解。
示例 1
'.'，得到唯一解。模拟答题者思考
1. 我先想暴力：统计空格数 m，对每个空格枚举 1-9，共 9^m 种组合，再逐个检查行、列、宫是否合法——思路对，但无效组合占绝大多数。
2. 重复在哪里？每填一格，子问题变成「在当前已填前缀上继续填下一个空格」；很多分支在填到一半时就会因行/列/宫冲突而注定失败，却还要把后面空格全部试完。
3. 关键转化：用与 #36 相同的 rows/cols/boxes 三套集合做 O(1) 合法性判断；DFS 找到下一个 '.'，依次尝试 1-9，能放就递归，子树无解立刻撤销换数字——经典回溯剪枝。
4. 例 1 第一格空格 (0,2)：先试 '1' 会与同行 '3' 冲突被剪枝，最终找到 '4' 合法后深入下一空格；任一路径走不通就回退改选。
5. 题目保证唯一解，找到第一个完整合法填法即可返回；最坏 O(9^m)，剪枝后远好于全枚举；递归深度 ≤ 空格数 m ≤ 81。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
rows[i] | set<char> × 9 | 定义：第 i 行已占用的数字集合维护：回溯过程中， rows[i] 始终等于当前盘上第 i 行所有非空格数字更新：在 (r,c) 填入 d 时 rows[r].add(d)；撤销时 rows[r].remove(d) |
cols[j] | set<char> × 9 | 定义：第 j 列已占用的数字集合维护：与行对称，保证列内 1-9 不重复更新：填数时加入、回溯时移除，与 rows 同步 |
boxes[b] | set<char> × 9 | 定义：第 b 个 3×3 宫已占用的数字，b = (r//3)*3 + c//3维护：与行、列约束并行，任意时刻三套集合互不矛盾 更新：尝试数字 d 前查 d not in boxes[b]；填入/撤销与行列一致 |
(r, c) | int, int | 定义：当前待填空格坐标，按行优先扫描得到 维护：每轮递归只处理一个空格，填完递归下一格，失败则换数字或回溯 更新： find_empty() 返回下一个 '.' 的位置；无空格时回溯成功终止 |
d | char | 定义：当前尝试填入的数字 '1'..'9'维护：仅当 d 不在 rows[r]/cols[c]/boxes[b] 时才合法更新：合法则写入 board[r][c]=d 并递归；子调用失败则撤销并试下一个 d |
落码步骤
1. 初始化 rows, cols, boxes 三套集合，扫描初始盘把已有数字登记进去
2. 定义 find_empty()：按行优先找第一个 board[r][c]=='.'，返回坐标；找不到说明已解完
3. 定义 backtrack()：调用 find_empty()，无空格则返回 True
4. 对当前空格 (r,c)，令 b=(r//3)*3+c//3，依次尝试 d='1'..'9'
5. 若 d 不在三套集合中：写入 board 并更新集合 → 递归 backtrack() → 成功则返回 True，否则撤销填数和集合
6. 九个数都失败则返回 False；从 backtrack() 启动，解直接写回原 board
代码实现
class Solution:
def solveSudoku(self, board: list[list[str]]) -> None:
rows = [set() for _ in range(9)]
cols = [set() for _ in range(9)]
boxes = [set() for _ in range(9)]
for i in range(9):
for j in range(9):
c = board[i][j]
if c != '.':
b = (i // 3) * 3 + j // 3
rows[i].add(c)
cols[j].add(c)
boxes[b].add(c)
def find_empty() -> tuple[int, int] | None:
for i in range(9):
for j in range(9):
if board[i][j] == '.':
return i, j
return None
def backtrack() -> bool:
pos = find_empty()
if pos is None:
return True
r, c = pos
b = (r // 3) * 3 + c // 3
for d in map(str, range(1, 10)):
if d in rows[r] or d in cols[c] or d in boxes[b]:
continue
board[r][c] = d
rows[r].add(d)
cols[c].add(d)
boxes[b].add(d)
if backtrack():
return True
board[r][c] = '.'
rows[r].remove(d)
cols[c].remove(d)
boxes[b].remove(d)
return False
backtrack()class Solution {
public:
void solveSudoku(vector<vector<char>>& board) {
vector<unordered_set<char>> rows(9), cols(9), boxes(9);
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
char c = board[i][j];
if (c == '.') continue;
int b = (i / 3) * 3 + j / 3;
rows[i].insert(c);
cols[j].insert(c);
boxes[b].insert(c);
}
}
function<bool()> backtrack = [&]() -> bool {
int r = -1, c = -1;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] == '.') { r = i; c = j; break; }
}
if (r != -1) break;
}
if (r == -1) return true;
int b = (r / 3) * 3 + c / 3;
for (char d = '1'; d <= '9'; d++) {
if (rows[r].count(d) || cols[c].count(d) || boxes[b].count(d))
continue;
board[r][c] = d;
rows[r].insert(d);
cols[c].insert(d);
boxes[b].insert(d);
if (backtrack()) return true;
board[r][c] = '.';
rows[r].erase(d);
cols[c].erase(d);
boxes[b].erase(d);
}
return false;
};
backtrack();
}
};
// 最坏 O(9^m)，m 为空格数；空间 O(m) 递归栈复杂度分析
O(9^m)
O(m)（递归栈，m 为空格数）
常见坑
回溯不撤销：填入数字后递归失败，必须把 board[r][c] 还原为 '.' 并从三套集合中 remove，否则污染兄弟分支。
宫格编号公式写错：应是 (r//3)*3 + c//3，与 #36 有效数独相同。
返回值误用：函数签名是 void，解直接写回 board，不要 return board；找到解后立刻返回，不必继续搜索其他可能（题目保证唯一解）。
必测边界 Case
仅剩 1-2 个 '.' → 回溯深度极浅，几乎 O(1)
初始盘大量 '.' → 依赖剪枝，暴力 9^m 不可接受
board 存 '1'..'9' 和 '.' 字符，不是 int
找到第一个完整合法填法即可停止，无需枚举所有解
按题面输入应得到唯一输出矩阵，修改原 board 而非返回新数组