企业官网建设流程全解析

• 教程
• 文档
• 知识库

本文是「算法通关手册」中 LeetCode 0037 解数独（Sudoku Solver） 题解的深度展开，围绕「回溯算法」这一核心方法，从题目约束、三重循环枚举、有效性校验到复杂度分析逐层拆解。读完本文，你将掌握用「选择 - 递归 - 回溯」三步法求解 9×9 数独的完整套路，并理解它与 有效的数独、N 皇后等经典回溯题的异同。

一、题目概述

题目链接

• 题号：0037 解数独（Sudoku Solver，力扣困难题）
• 标签：数组、哈希表、回溯、矩阵
• 难度：困难

题目大意

给定一个用二维字符数组board表示的数独棋盘：

• 数字1 ~ 9表示该位置已经填入了数字；
• 字符.表示该位置还没有填入数字。

要求：编写程序，通过填充空格的方式解决数独问题。最终不需要返回答案，只需将题目给定的board原地（in-place）修改为可行方案即可。

题目说明

数独解法必须遵循如下三条规则：

同时题目保证：

• board.length == 9，board[i].length == 9；
• board[i][j]是一位数字或者.；
• 题目数据保证输入数独仅有一个解（这是回溯法可行的前提：一旦找到可行解即可直接返回）。

示例

输入棋盘（.表示待填空格）：

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"]]

解出后的棋盘：

board = [["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"]]

二、前置知识：回溯算法回顾

回溯算法是本题的灵魂。手册在 07_algorithm/07_04_backtracking_algorithm.md 中对其作了系统讲解：回溯算法是一种通过递归和试错，系统地搜索所有可能解的算法，核心思想是「走不通就退回，换条路再试」。

回溯算法的通用模板如下（摘自 回溯算法章节）：

def backtrack(参数): if 终止条件: 处理结果 return for 选择 in 可选列表: if 满足约束: 做选择 backtrack(新参数) 撤销选择

把模板落地需要三个步骤：

1. 明确所有选择：画出决策树，理清每一步有哪些可选项；
2. 明确终止条件：通常是递归到某一深度、遍历完所有元素或满足题目要求；
3. 将决策树与终止条件转化为代码：定义回溯函数、书写「选择 - 递归 - 撤销选择」主体、明确递归终止及结果处理。

解数独正是这个模板的「困难模式」：可选项是每个空位上的1 ~ 9，约束条件升级为「行 / 列 / 宫格三重唯一性」，终止条件是 81 个格子全部被合法填满。

三、解题思路：回溯算法

3.1 思路框架

对于每一行、每一列、每一个数字，都需要一重for循环来遍历，这样整体就是三重for循环：

1. 第一重循环：遍历行i；
2. 第二重循环：遍历列j；
3. 第三重循环：当board[i][j]是空位时，遍历数字k（1 ~ 9）尝试填入。

对于第i行、第j列的元素来说：

• 如果当前位置是空位，则尝试将数字k置于此处，并调用校验函数判断数独是否仍然有效；
• 如果有效，则继续递归遍历下一个空位，直到遍历完所有空位得到可行方案，或某条分支全部失败而结束；
• 遍历完下一个空位（递归返回）之后，再将此位置**回退（回溯）**置为.，以尝试数字k+1或其他位置的其他选择。

3.2 校验函数 isValid 详解

isValid(row, col, val, board)负责在尝试把数字val放到(row, col)之前，快速判断是否违背三条约束，它包含三个独立检查：

def isValid(self, row: int, col: int, val: int, board: List[List[str]]) -> bool: # 1. 行检查：第 row 行是否已出现过 val for i in range(0, 9): if board[row][i] == str(val): return False # 2. 列检查：第 col 列是否已出现过 val for j in range(0, 9): if board[j][col] == str(val): return False # 3. 宫格检查：(row, col) 所在的 3×3 宫格内是否已出现过 val start_row = (row // 3) * 3 start_col = (col // 3) * 3 for i in range(start_row, start_row + 3): for j in range(start_col, start_col + 3): if board[i][j] == str(val): return False return True

三个检查点分别对应题目说明中的行、列、宫格三条规则：

• 行检查：固定row，扫描第row行的 9 个格子；
• 列检查：固定col，扫描第col列的 9 个格子；
• 宫格检查：关键在宫格定位。(row // 3) * 3得到宫格的起始行，(col // 3) * 3得到宫格的起始列，再遍历3 × 3的 9 个格子。例如row = 5, col = 7时，start_row = 3, start_col = 6，检查的是第 3~5 行、第 6~8 列组成的右下宫格。

注意：这里每尝试一个数字都要做一次O(9 + 9 + 9) = O(27)的线性扫描，属于常数级开销，胜在实现简单直观。

3.3 回溯主函数

def backtrack(self, board: List[List[str]]): for i in range(len(board)): # 第一重循环：遍历行 for j in range(len(board[0])): # 第二重循环：遍历列 if board[i][j] != '.': # 已填数字的位置直接跳过 continue for k in range(1, 10): # 第三重循环：尝试数字 1 ~ 9 if self.isValid(i, j, k, board): # 约束校验 board[i][j] = str(k) # 做选择：填入数字 if self.backtrack(board): # 递归：继续填下一个空位 return True # 找到可行解，逐层返回 board[i][j] = '.' # 撤销选择：回溯 return False # 当前空位 1~9 都失败，向上返回 False return True # 所有空位填满，得到可行解

逐步拆解这段递归逻辑：

1. 定位空位：双重循环从左到右、从上到下扫描棋盘，跳过已填数字的位置；
2. 尝试候选：对每个空位依次尝试1 ~ 9，用isValid过滤掉违反三条规则的候选；
3. 做选择：把合法候选写入board[i][j]（注意题目用字符数组，需str(k)转换）；
4. 递归深入：带着新状态继续调用backtrack，去填下一个空位；
5. 早停返回：一旦某次递归返回True，说明后续所有空格都已被合法填满，直接一路返回True，不再回溯；
6. 撤销选择：如果递归返回False，说明当前候选无法导向可行解，把位置恢复为.，尝试下一个候选；
7. 穷尽分支：如果1 ~ 9全部失败，返回False，让上层尝试其他数字。

整个搜索过程可以用一棵决策树描述：树的每一层对应一个空位，每个节点的分支对应1 ~ 9的候选数字，isValid是分支的过滤阀，找到叶子节点即找到一个完整解。这正是 回溯算法章节 中「决策树 + 终止条件 + 递归模板」三步走的直接体现。

四、完整代码

将上述两部分合并，得到完整的可运行解法（保留题目要求的原地修改语义）：

class Solution: def backtrack(self, board: List[List[str]]): for i in range(len(board)): for j in range(len(board[0])): if board[i][j] != '.': continue for k in range(1, 10): if self.isValid(i, j, k, board): board[i][j] = str(k) if self.backtrack(board): return True board[i][j] = '.' return False return True def isValid(self, row: int, col: int, val: int, board: List[List[str]]) -> bool: for i in range(0, 9): if board[row][i] == str(val): return False for j in range(0, 9): if board[j][col] == str(val): return False start_row = (row // 3) * 3 start_col = (col // 3) * 3 for i in range(start_row, start_row + 3): for j in range(start_col, start_col + 3): if board[i][j] == str(val): return False return True def solveSudoku(self, board: List[List[str]]) -> None: self.backtrack(board) """ Do not return anything, modify board in-place instead. """

运行方式与边界：

• 入口是solveSudoku(board)，它直接调用backtrack(board)原地修改棋盘，无返回值（与 LeetCode 题目签名一致）；
• 输入必须是标准的9 × 9字符数组，数字以字符串形式存储，空位用.；
• 题目保证输入数独仅有一个解，因此第一个完整解即可返回，无需收集所有解。

五、复杂度分析

时间复杂度：O(9^m)

• 设棋盘中.的数量为m（空位个数）；
• 每个空位最多尝试9个候选数字，因此最坏情况下搜索空间是9^m个状态；
• 每个状态还要做常数级的isValid校验（扫描行、列、宫格共 27 个格子），这部分开销是常数；
• 因此整体时间复杂度为O(9^m)，其中m是棋盘中.的数量。当棋盘几乎全空时（m接近 81），最坏情况是指数级爆炸；而实际数独题目的空位数量与初始给定数字共同决定了运行时间。

空间复杂度：O(9^2)

• 递归调用栈的最大深度取决于空位数量m，但棋盘本身是固定9 × 9；
• 校验与回溯均只使用常数规模的额外空间，因此空间复杂度为O(9^2)（即常数级，81 个格子的棋盘规模）。

关于复杂度记号的含义，可以参考手册中的 算法复杂度章节：大 O 表示渐近上界，反映最坏情况下的增长趋势。

六、进阶讨论：剪枝与优化方向

原始回溯解法胜在正确性与可读性，但O(9^m)的最坏复杂度意味着当空位较多时搜索会非常慢。从算法层面可以推断以下优化方向（属于通用算法知识，读者可在理解本题后自行尝试）：

1. 位运算状态压缩：用 9 个 bit 的整数分别记录每行、每列、每个宫格中已出现的数字，把isValid的线性扫描降为O(1)的位运算判断，同时做「填数 - 恢复」时也只需异或操作；
2. 最少候选优先（MRV）：每次递归前扫描所有空位，优先填充候选数字最少的格子（而不是简单从左到右），可以大幅剪枝、显著减少搜索树规模；
3. 提前校验：在填数前用「只出现一次的候选」启发式，或先跑一遍 0036 有效的数独 的思路确认初始盘面合法，避免在非法盘面上做无用搜索。

需要注意的是，本仓库题解文档以「回溯 + 线性校验」的标准做法为准，以上优化属于对该主题的延伸思考，适合作为后续练习方向。

七、与其他题目的关联

7.1 与 0036 有效的数独的关系

0036 有效的数独 只要求验证已填入的数字是否满足规则（用 3 个哈希表分别记录行、列、宫格），不要求求解；而本题要求求解完整数独。两者共用同一条规则体系，可以把 0036 看成解数独的「合法性验证子问题」——isValid检查的就是局部版本的「有效数独」。

7.2 回溯家族题目

在手册的 回溯算法题目列表 中，0037 解数独与以下题目同属回溯专题，推荐按难度递进练习：

• 0051 N 皇后（困难）：同样是「逐位置尝试 + 合法性校验 + 回溯」结构，区别是约束为行、列、斜线；
• 0046 全排列（中等）：回溯入门题，体会「选择 - 递归 - 回溯」最小模板；
• 0078 子集（中等）：每个元素「选 / 不选」两种分支；
• 0039 组合总和（中等）：在候选集合上做组合式回溯；
• 0079 单词搜索（中等）：在二维网格上做 DFS 式回溯；
• 0093 复原 IP 地址（中等）：对字符串做分段式回溯。

其中 N 皇后 与解数独在结构上最为接近：两者都是「在网格上逐格/逐行做选择，用校验函数过滤冲突，冲突则回溯」，可以对照阅读，进一步巩固回溯算法的「决策树 + 剪枝」思维。

• 教程
• 文档
• 知识库