引言 (Introduction)
前两篇文章中，我们处理的对象都是"从数组中选或不选"——子集、排列、组合的本质都是在 $n$ 个元素上做选择。本篇文章将回溯的视野拓展到更复杂的结构：字符串的切割线和二维棋盘的约束体系。
本文是本系列第三篇，聚焦于分割问题（Partitioning）与棋盘问题（N-Queens & Sudoku）。这两类问题的共同特点是：状态的定义不再是简单的 path 列表，而是需要维护切割位置、棋盘坐标、以及多维度的约束标记（行列、对角线、子方格）。我们将看到，回溯模板的 for 循环结构仍然是骨架，但状态管理变得更加精密。
1. 分割回文串（LeetCode 131）
1.1 问题分析
题目：给定一个字符串 s，将 s 分割成若干子串，使得每个子串都是回文串。返回所有可能的分割方案。
示例：s = "aab" → [["a", "a", "b"], ["aa", "b"]]
这道题的核心是将"切割线"抽象为状态。我们可以这样建模：
- 在
s的每个字符间隙插入"虚拟切割线"，用索引start标记当前切割的起点。 - 从
start出发，枚举所有可能的切割终点end。 - 如果
s[start:end+1]是回文，则将它加入当前分割方案，递归处理剩余部分s[end+1:]。
s = "a a b"
↑ ↑ ↑
0 1 2
决策树（切割视角）：
start=0
/ | \
"a"(0,0) "aa"(0,1) "aab"(0,2) ← 非回文，剪枝
start=1 start=2
/ \ \
"a"(1,1) "ab"(1,2) "b"(2,2)
start=2 ✗ 剪枝 start=3 → 记录结果
|
"b"(2,2) → start=3 → 记录 ["a","a","b"]
复杂度分析：
- 最坏情况（如
s = "aaa"）：每个子串都是回文，位置 $i$ 处有 $O(2^{N-i})$ 种分割方式。 - 总方案数上界为 $O(2^N)$（每个间隙可选"切"或"不切"），每个方案拷贝成本 $O(N)$。
- 时间复杂度：$O(N \cdot 2^N)$。
1.2 完整代码
from typing import List
class Solution:
def partition(self, s: str) -> List[List[str]]:
res: List[List[str]] = []
path: List[str] = []
def is_palindrome(left: int, right: int) -> bool:
"""判断 s[left:right+1] 是否为回文"""
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
def dfs(start: int) -> None:
if start == len(s): # 切割线到达末尾
res.append(path[:])
return
for end in range(start, len(s)):
if is_palindrome(start, end): # 剪枝：非回文直接跳过
path.append(s[start:end + 1]) # 选择该段切割
dfs(end + 1) # 下一段从 end+1 开始
path.pop() # 回溯
dfs(0)
return res
1.3 优化：DP 预处理回文
上述代码在每次判断回文时都做 $O(N)$ 扫描，可以使用动态规划预计算所有子串的回文性，将判断降为 $O(1)$：
def partition_dp(self, s: str) -> List[List[str]]:
n = len(s)
# dp[i][j] = s[i:j+1] 是否为回文
dp: List[List[bool]] = [[False] * n for _ in range(n)]
for right in range(n):
for left in range(right + 1):
if s[left] == s[right] and (right - left <= 2 or dp[left + 1][right - 1]):
dp[left][right] = True
res: List[List[str]] = []
path: List[str] = []
def dfs(start: int) -> None:
if start == n:
res.append(path[:])
return
for end in range(start, n):
if dp[start][end]: # O(1) 查询
path.append(s[start:end + 1])
dfs(end + 1)
path.pop()
dfs(0)
return res
DP 状态转移的直觉：s[left:right+1] 是回文，当且仅当 s[left] == s[right]且去掉首尾后的子串 s[left+1:right] 也是回文。边界条件 right - left <= 2 覆盖了长度为 1、2、3 的基础情况。
2. N 皇后（LeetCode 51）
2.1 问题建模
题目：在 $N \times N$ 的棋盘上放置 $N$ 个皇后，使得它们互不攻击（皇后可以攻击同行、同列、同对角线）。返回所有可能的放置方案。
这是回溯算法最经典的棋盘问题。其核心是逐行放置的视角转换：
- 以行为递归层级：第
row行放置一个皇后，尝试该行的每一列。 - 约束条件：不能与已放置的皇后冲突（同列、同主对角线、同副对角线）。
2.2 约束的数学建模
设第 row 行的皇后放在第 col 列。两个皇后不冲突的条件：
- 不同列：
col各不相同。 - 不同主对角线：主对角线上的格子满足
row - col = const（常数）。 - 不同副对角线：副对角线上的格子满足
row + col = const（常数）。
这个建模将"两个皇后是否在同一条对角线上"从 $O(N^2)$ 的循环检查降为了 $O(1)$ 的哈希集合查找。
2.3 完整代码
from typing import List
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
res: List[List[str]] = []
# board[row] = col，第 row 行的皇后放在第 col 列
board: List[int] = [-1] * n
# 已占用的列、主对角线、副对角线
cols: set[int] = set()
diag1: set[int] = set() # row - col
diag2: set[int] = set() # row + col
def dfs(row: int) -> None:
if row == n:
# 将 board 转化为字符串表示
solution: List[str] = []
for r in range(n):
line = ['.'] * n
line[board[r]] = 'Q'
solution.append(''.join(line))
res.append(solution)
return
for col in range(n):
if col in cols or (row - col) in diag1 or (row + col) in diag2:
continue # 剪枝：冲突
# 放置皇后
board[row] = col
cols.add(col)
diag1.add(row - col)
diag2.add(row + col)
dfs(row + 1) # 进入下一行
# 移除皇后（回溯）
cols.discard(col)
diag1.discard(row - col)
diag2.discard(row + col)
dfs(0)
return res
复杂度分析：
- 时间复杂度：上界 $O(N!)$。第 1 行有 $N$ 种选择，第 2 行受限约 $N-2$ 种，……
- 实际运行远小于 $N!$，因为对角线剪枝非常强力（每条对角线最多放一个皇后，共 $2N-1$ 条对角线，天然上限 $2N-1$ 个皇后）。
2.4 更简洁的位运算写法
对于追求极致效率的场景，可以使用位运算替代集合。这里仅展示核心思想：
def solveNQueens_bit(self, n: int) -> List[List[str]]:
"""位运算 N 皇后（只展示计数版本，完整版本类似）"""
def dfs(row: int, col_mask: int, diag1_mask: int, diag2_mask: int) -> int:
if row == n:
return 1
count = 0
# 可放置的列：取反后去掉高位保留 n 位
available = ((1 << n) - 1) & ~(col_mask | diag1_mask | diag2_mask)
while available:
pos = available & -available # 取最低位的 1
available ^= pos # 清除该位
count += dfs(row + 1,
col_mask | pos,
(diag1_mask | pos) << 1, # 主对角线向下一行左移
(diag2_mask | pos) >> 1) # 副对角线向下一行右移
return count
return dfs(0, 0, 0, 0)
对角线位移的直觉：主对角线走到下一行后向左偏移（<< 1），副对角线走到下一行后向右偏移（>> 1）。这个奇妙的性质来自对角线的几何定义——相邻两行同一主对角线上的格子列索引相差 $+1$。
3. 解数独（LeetCode 37）
3.1 问题分析
题目：编写一个程序来解数独。空白格用 '.' 表示。数独解法需遵循规则：数字 1-9 在每一行、每一列、每一个 $3 \times 3$ 宫内只能出现一次。
这是回溯算法在高维约束下的经典应用。与 N 皇后不同，数独的状态空间是二维的，需要在 $9 \times 9 = 81$ 个格子上进行决策。
3.2 状态建模与剪枝
三种状态的快速查询——我们需要在 $O(1)$ 时间内判断某个格子是否能填某个数字：
# row[i][d] = 第 i 行是否已有数字 d
# col[j][d] = 第 j 列是否已有数字 d
# box[k][d] = 第 k 个 3×3 宫是否已有数字 d
# 其中 k = (i // 3) * 3 + (j // 3)
搜索顺序优化：优先填可选数字最少的空格（最少候选数优先），这是数独回溯中最重要的启发式优化，可以将暴力搜索的时间从几分钟降低到毫秒级。
3.3 完整代码
from typing import List, Optional
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
"""原地修改 board"""
# 状态数组：True 表示数字已被占用
row: List[List[bool]] = [[False] * 10 for _ in range(9)]
col: List[List[bool]] = [[False] * 10 for _ in range(9)]
box: List[List[bool]] = [[False] * 10 for _ in range(9)]
empty_cells: List[tuple[int, int]] = []
# 初始化：标记已有数字
for i in range(9):
for j in range(9):
if board[i][j] != '.':
d = int(board[i][j])
row[i][d] = True
col[j][d] = True
box[(i // 3) * 3 + (j // 3)][d] = True
else:
empty_cells.append((i, j))
def dfs(idx: int) -> bool:
"""返回 True 表示找到解，停止搜索"""
if idx == len(empty_cells):
return True # 所有空格已填完
i, j = empty_cells[idx]
k = (i // 3) * 3 + (j // 3)
for d in range(1, 10):
if row[i][d] or col[j][d] or box[k][d]:
continue # 剪枝：冲突
# 放置数字
board[i][j] = str(d)
row[i][d] = col[j][d] = box[k][d] = True
if dfs(idx + 1):
return True # 找到解，链式返回
# 撤销（回溯）
board[i][j] = '.'
row[i][d] = col[j][d] = box[k][d] = False
return False # 所有数字都尝试失败
dfs(0)
dfs 返回 bool 而非 void 的设计理由：
- 数独只需要一个解，找到后应立即终止搜索。
- 返回
True并链式传递，避免了在找到解后继续做无意义的回溯。 - 这与子集/排列的"枚举所有解"模式不同——回溯的返回值设计取决于问题需要一个解还是全部解。
3.4 最少候选数优先优化
def solveSudoku_optimized(self, board: List[List[str]]) -> None:
"""最少候选数优先（MRV 启发式）"""
row = [[False] * 10 for _ in range(9)]
col = [[False] * 10 for _ in range(9)]
box = [[False] * 10 for _ in range(9)]
for i in range(9):
for j in range(9):
if board[i][j] != '.':
d = int(board[i][j])
row[i][d] = col[j][d] = box[(i // 3) * 3 + (j // 3)][d] = True
def count_candidates(i: int, j: int) -> int:
"""计算格子 (i, j) 的可选数字个数"""
k = (i // 3) * 3 + (j // 3)
return sum(1 for d in range(1, 10)
if not (row[i][d] or col[j][d] or box[k][d]))
def dfs() -> bool:
# 找可选数字最少的空格
min_candidates = 10
best_cell: Optional[tuple[int, int]] = None
for i in range(9):
for j in range(9):
if board[i][j] == '.':
cnt = count_candidates(i, j)
if cnt == 0:
return False # 无解，提前返回
if cnt < min_candidates:
min_candidates = cnt
best_cell = (i, j)
if cnt == 1:
break # 只有 1 个候选，不必再找
if min_candidates == 1:
break
if best_cell is None:
return True # 所有格子已填
i, j = best_cell
k = (i // 3) * 3 + (j // 3)
for d in range(1, 10):
if row[i][d] or col[j][d] or box[k][d]:
continue
board[i][j] = str(d)
row[i][d] = col[j][d] = box[k][d] = True
if dfs():
return True
board[i][j] = '.'
row[i][d] = col[j][d] = box[k][d] = False
return False
dfs()
MRV（Minimum Remaining Values）启发式是 CSP（约束满足问题）中通用的剪枝策略：优先给约束最强的变量赋值，因为它的选择最少，最容易失败，越早发现失败越省钱。
4. 分割与棋盘的统一视角
尽管分割回文串、N 皇后、解数独三者的具体建模差异很大，但它们共享同一套回溯哲学：
| 问题 | 状态 | 约束建模 | 剪枝方式 |
|---|---|---|---|
| 分割回文串 | start（切割线位置） |
is_palindrome(left, right) |
非回文子串直接跳过 |
| N 皇后 | board[row] = col |
cols, diag1, diag2 集合 |
冲突直接跳过 |
| 解数独 | board[i][j] = d |
row[9][10], col[9][10], box[9][10] |
已占用直接跳过 + MRV 启发式 |
共同模式：
- 状态按层级递进：分割按切割线、皇后按行、数独按空格列表。
- 约束用哈希结构表达：集合或布尔数组，将冲突检测从 $O(N)$ 降至 $O(1)$。
- 剪枝即约束传播：一旦发现当前部分赋值违反了约束，立即停止深入——这就是约束满足问题（CSP）中的"向前检查"思想。
结论 (Conclusion)
本文从一维的切割线（回文分割）推进到二维的棋盘约束（N 皇后、数独），展示了回溯算法在复杂状态空间中的建模能力。核心认识：
- 状态的抽象层次决定了代码的清晰度。切割线用
start索引、棋盘用row索引、数独用空格列表——每个问题都有一个最自然的"递归层级"。 - 约束的表达比约束的检查更重要。
row - col建模主对角线、(i//3)*3 + (j//3)建模九宫格——找到正确的数学表达，代码复杂度可以大幅下降。 - 回溯与 CSP 的关系：N 皇后和数独的本质是约束满足问题，回溯作为 CSP 的求解引擎，剪枝则对应约束传播。
下一篇（最终篇）将进入二维网格搜索与高级技巧——包括单词搜索中的 Trie+回溯组合、IP 地址复原的约束剪枝，并在最后为整个系列做出全面的复盘对照表。