题目描述
思路解析动画文字版
核心三步：找空格 → 试 1-9 查冲突 → 合法就填并递归，不行就回溯换数。
这是起始盘：绿色是题目给定的数字（固定不动），浅蓝是要填的 12 个空格。从左上角第一个空格开始。
轮到空格 (0,2)。从 1 开始往上试，逐个检查放进去会不会和同行、同列、同宫的数字撞。
(0,2) 试 1：同行/同列/同宫里已经有 1 了，撞了，擦掉换下一个。
(0,2) 试 2：同行/同列/同宫里已经有 2 了，撞了，擦掉换下一个。
(0,2) 试 3：同行/同列/同宫里已经有 3 了，撞了，擦掉换下一个。
(0,2) 试 4：同行、同列、同宫都没有 4，合法！填进去，去找下一个空格。
轮到空格 (0,6)。从 1 开始往上试，逐个检查放进去会不会和同行、同列、同宫的数字撞。
(0,6) 试 1：同行/同列/同宫里已经有 1 了，撞了，擦掉换下一个。
(0,6) 试 2：同行/同列/同宫里已经有 2 了，撞了，擦掉换下一个。
(0,6) 试 3：同行/同列/同宫里已经有 3 了，撞了，擦掉换下一个。
(0,6) 试 4：同行/同列/同宫里已经有 4 了，撞了，擦掉换下一个。
(0,6) 试 5：同行/同列/同宫里已经有 5 了，撞了，擦掉换下一个。
(0,6) 试 6：同行/同列/同宫里已经有 6 了，撞了，擦掉换下一个。
(0,6) 试 7：同行/同列/同宫里已经有 7 了，撞了，擦掉换下一个。
(0,6) 试 8：同行/同列/同宫里已经有 8 了，撞了，擦掉换下一个。
(0,6) 试 9：同行、同列、同宫都没有 9，合法！填进去，去找下一个空格。
轮到空格 (1,3)。从 1 开始往上试，逐个检查放进去会不会和同行、同列、同宫的数字撞。
(1,3) 试 1：同行、同列、同宫都没有 1，合法！填进去，去找下一个空格。
轮到空格 (1,7)。从 1 开始往上试，逐个检查放进去会不会和同行、同列、同宫的数字撞。
(1,7) 试 1：同行/同列/同宫里已经有 1 了，撞了，擦掉换下一个。
(1,7) 试 2：同行/同列/同宫里已经有 2 了，撞了，擦掉换下一个。
(1,7) 试 3：同行/同列/同宫里已经有 3 了，撞了，擦掉换下一个。
(1,7) 试 4：同行、同列、同宫都没有 4，合法！填进去，去找下一个空格。
轮到空格 (2,0)。从 1 开始往上试，逐个检查放进去会不会和同行、同列、同宫的数字撞。
(2,0) 试 1：同行、同列、同宫都没有 1，合法！填进去，去找下一个空格。
轮到空格 (2,5)。从 1 开始往上试，逐个检查放进去会不会和同行、同列、同宫的数字撞。
(2,5) 试 1：同行/同列/同宫里已经有 1 了，撞了，擦掉换下一个。
(2,5) 试 2：同行、同列、同宫都没有 2，合法！填进去，去找下一个空格。
轮到空格 (4,4)。从 1 开始往上试，逐个检查放进去会不会和同行、同列、同宫的数字撞。
(4,4) 试 1：同行/同列/同宫里已经有 1 了，撞了，擦掉换下一个。
(4,4) 试 2：同行/同列/同宫里已经有 2 了，撞了，擦掉换下一个。
(4,4) 试 3：同行/同列/同宫里已经有 3 了，撞了，擦掉换下一个。
(4,4) 试 4：同行/同列/同宫里已经有 4 了，撞了，擦掉换下一个。
(4,4) 试 5：同行、同列、同宫都没有 5，合法！填进去，去找下一个空格。
轮到空格 (5,1)。从 1 开始往上试，逐个检查放进去会不会和同行、同列、同宫的数字撞。
(5,1) 试 1：同行、同列、同宫都没有 1，合法！填进去，去找下一个空格。
轮到空格 (5,8)。从 1 开始往上试，逐个检查放进去会不会和同行、同列、同宫的数字撞。
(5,8) 试 1：同行/同列/同宫里已经有 1 了，撞了，擦掉换下一个。
(5,8) 试 2：同行/同列/同宫里已经有 2 了，撞了，擦掉换下一个。
(5,8) 试 3：同行/同列/同宫里已经有 3 了，撞了，擦掉换下一个。
(5,8) 试 4：同行/同列/同宫里已经有 4 了，撞了，擦掉换下一个。
(5,8) 试 5：同行/同列/同宫里已经有 5 了，撞了，擦掉换下一个。
(5,8) 试 6：同行、同列、同宫都没有 6，合法！填进去，去找下一个空格。
轮到空格 (7,2)。从 1 开始往上试，逐个检查放进去会不会和同行、同列、同宫的数字撞。
(7,2) 试 1：同行/同列/同宫里已经有 1 了，撞了，擦掉换下一个。
(7,2) 试 2：同行/同列/同宫里已经有 2 了，撞了，擦掉换下一个。
(7,2) 试 3：同行/同列/同宫里已经有 3 了，撞了，擦掉换下一个。
(7,2) 试 4：同行/同列/同宫里已经有 4 了，撞了，擦掉换下一个。
(7,2) 试 5：同行/同列/同宫里已经有 5 了，撞了，擦掉换下一个。
(7,2) 试 6：同行/同列/同宫里已经有 6 了，撞了，擦掉换下一个。
(7,2) 试 7：同行、同列、同宫都没有 7，合法！填进去，去找下一个空格。
轮到空格 (7,6)。从 1 开始往上试，逐个检查放进去会不会和同行、同列、同宫的数字撞。
(7,6) 试 1：同行/同列/同宫里已经有 1 了，撞了，擦掉换下一个。
(7,6) 试 2：同行/同列/同宫里已经有 2 了，撞了，擦掉换下一个。
(7,6) 试 3：同行/同列/同宫里已经有 3 了，撞了，擦掉换下一个。
(7,6) 试 4：同行/同列/同宫里已经有 4 了，撞了，擦掉换下一个。
(7,6) 试 5：同行/同列/同宫里已经有 5 了，撞了，擦掉换下一个。
(7,6) 试 6：同行、同列、同宫都没有 6，合法！填进去，去找下一个空格。
轮到空格 (8,4)。从 1 开始往上试，逐个检查放进去会不会和同行、同列、同宫的数字撞。
(8,4) 试 1：同行/同列/同宫里已经有 1 了，撞了，擦掉换下一个。
(8,4) 试 2：同行/同列/同宫里已经有 2 了，撞了，擦掉换下一个。
(8,4) 试 3：同行/同列/同宫里已经有 3 了，撞了，擦掉换下一个。
(8,4) 试 4：同行/同列/同宫里已经有 4 了，撞了，擦掉换下一个。
(8,4) 试 5：同行/同列/同宫里已经有 5 了，撞了，擦掉换下一个。
(8,4) 试 6：同行/同列/同宫里已经有 6 了，撞了，擦掉换下一个。
(8,4) 试 7：同行/同列/同宫里已经有 7 了，撞了，擦掉换下一个。
(8,4) 试 8：同行、同列、同宫都没有 8，合法！填进去，去找下一个空格。
所有空格都合法填满了，每行、每列、每宫的 1-9 都不重复——数独解出。
边界先想清。
两个高频追问。
参考代码
def solveSudoku(board): def valid(r, c, ch): for k in range(9): if board[r][k] == ch: return False # 同行 if board[k][c] == ch: return False # 同列 br, bc = r//3*3, c//3*3 for i in range(3): for j in range(3): if board[br+i][bc+j] == ch: return False # 同宫 return True def dfs(): for r in range(9): for c in range(9): if board[r][c] == ".": for ch in "123456789": if valid(r, c, ch): board[r][c] = ch if dfs(): return True board[r][c] = "." # 回溯 return False return True dfs()复杂度
- 时间：O(9^k)，k=空格数，每格最多试 9 个数（剪枝后远小于此）
- 空间：O(k)，递归栈深度 = 空格数；原地改盘不额外开盘
易错点
面试追问把动画讲成自己的话
追问怎么让数独求解更快？
追问怎么判断数独有没有唯一解？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
全排列 II
LeetCode 47 · 中等 · 沿着 回溯 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题