§1

题目描述

把数独棋盘填满。每行、每列、每个 3×3 宫里，1 到 9 都只能出现一次。空格用 . 表示，要原地填好。

board = 9×9 棋盘，部分已填，其余是 .

输出 = 原地把每个 . 填成唯一解

§2

思路解析动画文字版

假如有 50 个空格，每格瞎填 1 到 9，就是 9 的 50 次方种填法，宇宙毁灭都算不完。所以不能盲填，得边填边检查、错了立刻回头。

回溯三件套：在一个空格里挑一个不冲突的数填进去，往下递归填后面的格；要是后面怎么都填不通，就把这个数擦掉，回来换下一个试。

1. 锁定一个空格：我们把镜头对准左上角这个九宫格。算法找到的第一个空格在右上角，标成蓝色，现在要给它挑一个数。

2. 试 5 → 行里有 5：算法从 1 试到 9，挨个查。这里演示试到 5：本行最左已有 5（题目原本就给的），重复，跳过。

3. 试 3 → 行里有 3：再试 3。可这一行已经有个 3（也是题目给定的），又重复，继续划掉。检查靠的是「行、列、宫三个集合」，一查就知道行不行。

4. 试 1 → 通过，填入：试到 1：本行没 1、本列没 1、本宫也没 1，三关都过！把 1 填进去，标绿，然后递归去填下一个空格。

5. 往下走，后面全填不通：顺着 (0,2) 填 1 继续往下递归。可走到深处，某个空格 1 到 9 全都冲突，怎么填都不行，这条路死了，得往回退。

6. 撤销：擦掉刚填的 1：回到 (0,2)，把刚填的 1 擦掉，格子变回空，行、列、宫集合里的 1 也同步删掉。这一步是回溯的灵魂：不撤干净，后面就被污染。

7. 换 2 试 → 这条也死：在 (0,2) 换下一个候选 2，填进去往下递归。结果这条分支也走不通，再撤销 2，接着试下一个。

8. 换 4 试 → 这条路走得通：再换 4：填进去往下递归，这回这个宫先凑齐了——5 3 4 / 6 7 2 / 1 9 8。台上只演了左上这一角，其余 80 格同理一路递归填下去，全部填通才 return True 层层上报。

一句话本质：数独就是带「合法性剪枝」的回溯，每个空格挨个试数，错了就撤回来换，直到全盘填满。

雷区实演 · 撤销不彻底：看 BUG 现场:刚才在 (0,2) 试过 1，撤销时只把格子擦成点,却忘了 rows[0].discard('1')。于是集合里 1 还占着,这一行后面再也填不了 1，本来有解也被你判成无解。

三个高频追问:加速(MRV)、位掩码、为什么提前返回。

迁移阶梯：练熟这题，再去回溯专题迁移:N 皇后、单词搜索、组合/排列,都是「做选择→递归→撤销」的同一套骨架，换的只是「合法性怎么判」。卡住可问 AI 助教或去通关训练里实战。

边界三连：三种边界:全满、单格死路、唯一解,把它们想清楚，递归的进入与返回就不会写漏。

§3

参考代码

class Solution:    def solveSudoku(self, board):        rows = [set() for _ in range(9)]        cols = [set() for _ in range(9)]        boxes = [set() for _ in range(9)]        empty = []        for r in range(9):            for c in range(9):                ch = board[r][c]                if ch == '.':                    empty.append((r, c))                else:                    b = (r // 3) * 3 + c // 3                    rows[r].add(ch); cols[c].add(ch); boxes[b].add(ch)        def dfs(i):            if i == len(empty):                return True            r, c = empty[i]            b = (r // 3) * 3 + c // 3            for ch in '123456789':                if ch in rows[r] or ch in cols[c] or ch in boxes[b]:                    continue                board[r][c] = ch                rows[r].add(ch); cols[c].add(ch); boxes[b].add(ch)                if dfs(i + 1):                    return True                rows[r].discard(ch); cols[c].discard(ch); boxes[b].discard(ch)                board[r][c] = '.'            return False        dfs(0)

看懂代码不等于写得出。盖住上面，自己默写一遍试试。卡在哪一行说不清，就点右下角问小欧。

§4

复杂度

时间复杂度：O(9^e)，e=空格数，每格最多试 9 个数；但行列宫剪枝后实际分支远小于 9，几乎瞬间出解
空间复杂度：O(e)，递归深度最多 e 层，加上行列宫三组常数大小的集合

§5

可套用的代码模板

把上面参考代码抽成骨架:解数独只是给「候选列表」「合法性」「待填位置」填上数独的规则。换成 N 皇后、单词搜索，骨架不变，只改这三处。

def dfs(i):    if i == 待填位置总数:        # 全填完        return True    取出第 i 个待填位置    for 候选 in 候选列表:        if 候选不合法(查状态集合):   # 剪枝            continue        做选择(写入位置 + 状态集合加)        if dfs(i + 1):            return True        撤销选择(清空位置 + 状态集合删)  # 关键    return False

§6

易错点

✗ 错误写法：每填一个数就扫整行整列整宫判重

✓ 正确写法：用 rows/cols/boxes 三个集合 O(1) 查

每格都重扫 27 格，慢且易错；集合一查就知道能不能填

✗ 错误写法：回溯时只把 board 改回 .

✓ 正确写法：board 和三个集合都要同步删掉这个数

集合没撤干净，后面分支会以为这个数还占着，整盘判错

✗ 错误写法：宫下标算成 r*3+c

✓ 正确写法：b = (r // 3) * 3 + c // 3

要的是 0~8 的九宫格编号，先把行列都整除 3 再组合

面试追问把动画讲成自己的话

追问怎么加速？不想从 1 到 9 挨个试。

每次不挑第一个空格，而是挑「候选数字最少」的空格优先填(最少剩余值启发式 MRV)，能大幅砍掉分支，难局快几十倍。

追问用 set 和用位掩码(bitmask)有什么区别？

逻辑一样。位掩码用一个 int 的 9 个比特表示 1~9 用没用，加删查都是位运算，更省内存更快；面试写 set 更直观，竞赛常用 bitmask。

追问为什么填通了要一路 return True，而不是继续找？

数独保证唯一解，找到一组就够了。return True 让每一层立刻停下、不再试别的数，直接把成功结果上报到顶。

这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：

下一题 · 回溯 11/11

全排列 II

LeetCode 47 · 中等 · 沿着回溯继续往下推进

→

把这道题真正学会，再走

图解算法年卡 ¥99 /年

✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
✓学习报告，记录每道题的掌握程度

299道动画图解

37节语音讲解

28课数据结构

¥0.27折合 / 天

76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解

¥99 开通年卡 →

想成体系刷透这类套路？去图解算法专题

class Solution: def solveSudoku(self, board): rows = [set() for _ in range(9)] cols = [set() for _ in range(9)] boxes = [set() for _ in range(9)] empty = [] for r in range(9): for c in range(9): ch = board[r][c] if ch == '.': empty.append((r, c)) else: b = (r // 3) * 3 + c // 3 rows[r].add(ch); cols[c].add(ch); boxes[b].add(ch) def dfs(i): if i == len(empty): return True r, c = empty[i] b = (r // 3) * 3 + c // 3 for ch in '123456789': if ch in rows[r] or ch in cols[c] or ch in boxes[b]: continue board[r][c] = ch rows[r].add(ch); cols[c].add(ch); boxes[b].add(ch) if dfs(i + 1): return True rows[r].discard(ch); cols[c].discard(ch); boxes[b].discard(ch) board[r][c] = '.' return False dfs(0)

def dfs(i): if i == 待填位置总数: # 全填完 return True 取出第 i 个待填位置 for 候选 in 候选列表: if 候选不合法(查状态集合): # 剪枝 continue 做选择(写入位置 + 状态集合加) if dfs(i + 1): return True 撤销选择(清空位置 + 状态集合删) # 关键 return False