--- title: 回溯算法：组合、N 皇后与数独 date: "2015-02-14 22:10" tags: ["算法"] published: true --- 回溯算法（Backtracking）通过递归枚举选择；当前选择无法满足约束时，撤销最后一次状态修改并尝试其他选择。 最近练习 LeetCode 的组合求和（39）、组合（77）、N 皇后（51）和数独（37）时，数独集中涉及三个问题： 1. 决策树到底按什么分层？ 2. 递归函数该返回什么？ 3. 剪枝的边界在哪里？ ## 回溯的通用结构 无论题目怎么变，回溯算法都在做三件事： ```js function backtrack(路径, 选择列表) { if (满足结束条件) { 记录结果 return } for (选择 in 选择列表) { 做选择 // 修改状态 backtrack(路径) // 递归进入下一层 撤销选择 // 恢复状态，即"回溯" } } ``` 路径是已做出的决策集合，选择列表是当前可选项。关键在于：进入下一层前修改状态，返回后必须恢复原状。普通 DFS 通常遍历已存在的树或图；回溯在搜索过程中构造决策路径，多个分支共享同一份可变状态。若不撤销状态，下一个分支会继承上一个分支的选择。撤销操作保证各分支从相同的父状态开始。 在组合问题（LeetCode 77：从 1~n 选 k 个数）中，这个框架非常清晰： ```js var combine = function (n, k) { const res = [] const track = [] function backtrack(start) { if (track.length === k) { res.push([...track]) // 结束：凑够了 k 个 return } for (let i = start; i <= n; i++) { track.push(i) // 做选择 backtrack(i + 1) // 递归：下一层从 i+1 开始，避免重复 track.pop() // 撤销：弹出，回到上一层的状态 } } backtrack(1) return res } ``` 这里的决策点是"第几个位置填什么数"，选择列表是 `start ~ n`。树的每一层代表一个待填充的位置，`start` 参数保证了同一组合不会因为顺序不同被重复统计。 ## 组合总和的去重与剪枝 组合求和（LeetCode 39）在组合的基础上加了一个约束：所有数字之和恰好等于目标值 `target`，且同一个数字可以重复使用。 ```js var combinationSum = function (candidates, target) { const res = [] const track = [] candidates.sort((a, b) => a - b) // 排序是剪枝的前提 function backtrack(start, remain) { if (remain === 0) { res.push([...track]) return } for (let i = start; i < candidates.length; i++) { if (candidates[i] > remain) break // 剪枝：后面只会更大，直接停止本层循环 track.push(candidates[i]) backtrack(i, remain - candidates[i]) // 注意是 i 不是 i+1：允许重复选自己 track.pop() } } backtrack(0, target) return res } ``` 这道题揭示了两种不同性质的剪枝： - **去重剪枝**：`combine` 里的 `i + 1` 保证不会选到自己之前的位置，避免统计出重复组合。 - **无效剪枝**：`combinationSum` 里的 `candidates[i] > remain` 是在排序之后，利用单调性提前终止整段循环，而不是等递归深入之后再发现和超了才返回。 排序后，候选数组单调递增；当 `candidates[i] > remain` 时，后续候选项也无法满足剩余目标值，因此可以用 `break` 结束本层循环，而不是仅跳过当前分支。 ## N 皇后：按行选择列 N 皇后（LeetCode 51）需要在 `n×n` 棋盘上放置皇后。由于每行必须且只能放置一个皇后，搜索可以按行进行： > 不需要在 n² 个格子里选 n 个，只需要在第 0 行选一个列，第 1 行选一个列……第 n-1 行选一个列。 路径从 `track[]` 变成了 `track[row] = col`，即"第 row 行的皇后在第 col 列"。 冲突检测也变成了数学问题： - 同列：`col === c` - 主对角线：`row - col === r - c` - 副对角线：`row + col === r + c` 用三个 `Set` 记录已占用的列和两条对角线，冲突检测压缩到 O(1)： ```js const cols = new Set() const diag1 = new Set() // row - col const diag2 = new Set() // row + col // 做选择时 cols.add(col) diag1.add(row - col) diag2.add(row + col) // 撤销时 cols.delete(col) diag1.delete(row - col) diag2.delete(row + col) ``` 这是回溯算法的一个经典优化方向：把约束条件转化为状态集合，避免每次线性扫描棋盘。付出的代价是额外维护三份和路径同步增减的状态，好处是把每一步的合法性检测从 O(n) 降到 O(1)。 ## 数独的回溯实现 数独（LeetCode 37）同时包含三类约束： 1. 每行 1-9 不重复 2. 每列 1-9 不重复 3. 每个 3×3 宫内 1-9 不重复 而且与 N 皇后不同，数独有预设数字，搜索空间不规则，81 个格子里哪些是决策点、哪些不是，要在运行时判断。这带来三个容易被忽略的问题：决策点在哪一层循环、递归该返回什么类型、状态是拷贝还是原地修改，下面依次展开。 ### 4.1 循环顺序即树结构 数独代码里最容易写错的是循环嵌套顺序： ```js // 正确：先遍历空格（决策点），再遍历数字（选择项） function solveSudoku(board) { function backtrack() { for (let r = 0; r < 9; r++) { for (let c = 0; c < 9; c++) { if (board[r][c] !== '.') continue for (let num = 1; num <= 9; num++) { // 选择项 const ch = String(num) if (isValid(board, r, c, ch)) { board[r][c] = ch if (backtrack()) return true // 关键！ board[r][c] = '.' } } return false // 1-9 全不行，回溯 } } return true // 没有空格了，说明填完了 } backtrack() } ``` 为什么不能把 `for (num)` 放到行列循环外面？ 因为回溯树的分层依据是"决策点"，数独的决策点是空格，不是数字。每一层递归的语义是："处理当前这个空格，选一个合法的数字填进去。" 如果把数字放外层，语义变成了："先拿住数字 5，去所有空格找能填 5 的位置。"这会导致： - 同一个空格被重复尝试 - 递归回来时不知道上一个处理的是哪个空格 - 回溯链条彻底断裂，因为一次递归调用不再对应"确定一个格子"这个单一职责 核心原则：决策点在哪一层，哪一层就应该是循环的最外层；选择项永远在决策点内部展开。 ### 4.2 boolean 返回值控制搜索终止 数独的 `backtrack` 返回 `boolean`，这是与组合题最大的不同。 组合题要收集所有解，所以找到解时 `res.push([...track])`，然后继续搜索其他分支，函数本身不需要返回值。数独保证有且仅有一个解，找到后必须立即停止整棵搜索树的其余分支： ```js board[r][c] = ch // 做选择 if (backtrack()) { // 递归：问下一层"你搞定了吗？" return true // 下一层说搞定了，我也向上汇报搞定 } board[r][c] = '.' // 否则：撤销，试下一个数字 ``` 最底层（没有空格时）返回 `true`。每一层收到 `true` 后立即 `return true`，从而退出所有循环和递归。此时棋盘保留最终答案，因此该路径不能执行撤销操作。 收集所有解时，回溯函数通常使用 `void` 返回值并遍历完整个搜索树；只需一个解时，`boolean` 返回值用于表示是否继续搜索。 ### 4.3 原地修改：引用即答案 数独的 `board` 是二维数组，传入的是引用。`board[r][c] = '5'` 直接修改了原始数组。所以不需要像组合题那样把 `track` 拷贝进 `res`，最终 `board` 本身就是答案，函数甚至可以没有返回值意义上的"结果"，只有一个表示"是否成功"的信号。 这是回溯的另一种模式：原地修改加布尔信号，适用于"求解一个确定解"而非"收集所有解"的场景，好处是省掉了每次拷贝路径的开销。 ### 4.4 剪枝：三个方向的集合 与 N 皇后类似，数独用三个维度的判断来做约束检测： ```js function isValid(board, r, c, ch) { for (let i = 0; i < 9; i++) { if (board[r][i] === ch) return false // 行 if (board[i][c] === ch) return false // 列 } const boxR = Math.floor(r / 3) * 3 const boxC = Math.floor(c / 3) * 3 for (let i = 0; i < 3; i++) { for (let j = 0; j < 3; j++) { if (board[boxR + i][boxC + j] === ch) return false // 宫 } } return true } ``` 这里是 O(1) 空间换来一次 O(27) 的检测，如果每个格子都提前维护行、列、宫三张"已用数字"位图（用 9 位的整数或 `Set` 表示），检测可以进一步降到 O(1)，但对 9×9 的固定规模而言，直接扫描已经足够快，没必要为了理论上的常数优化牺牲代码可读性。 ### 4.5 启发式：MRV 优化 基础版是顺序扫描空格，从左到右、从上到下。进阶做法是 MRV（Minimum Remaining Values）：每次找候选数字最少的空格优先填。 ```js var solveSudoku = function(board) { // 检查在 (r, c) 放 num 是否合法 const isValid = (r, c, num) => { for (let i = 0; i < 9; i++) { if (board[r][i] === num || board[i][c] === num) return false; } const boxR = Math.floor(r / 3) * 3; const boxC = Math.floor(c / 3) * 3; for (let i = 0; i < 3; i++) { for (let j = 0; j < 3; j++) { if (board[boxR + i][boxC + j] === num) return false; } } return true; }; // 获取某个空格的所有候选数字 const getCandidates = (r, c) => { const nums = []; for (let i = 1; i <= 9; i++) { if (isValid(r, c, String(i))) nums.push(String(i)); } return nums; }; const backtrack = () => { let minOptions = 10; let bestR = -1, bestC = -1, bestNums = []; // MRV：扫描全盘，找候选数字最少的空格 for (let r = 0; r < 9; r++) { for (let c = 0; c < 9; c++) { if (board[r][c] !== '.') continue; const nums = getCandidates(r, c); if (nums.length < minOptions) { minOptions = nums.length; bestR = r; bestC = c; bestNums = nums; if (minOptions === 1) break; // 唯一候选，已经最优 } } if (minOptions === 1) break; } // 没有空格了，解完 if (bestR === -1) return true; // 只处理这个最优格子 for (const num of bestNums) { board[bestR][bestC] = num; if (backtrack()) return true; board[bestR][bestC] = '.'; } return false; }; backtrack(); }; ``` MRV 背后的直觉是：约束越紧的格子越应该先填，因为它出错的可能性最小，而且尽早暴露矛盾——如果某个格子的候选数字是 0 个，说明当前路径已经走不通，可以立刻回溯，不用等填完其他格子再发现矛盾。这本质上是把"failure 尽早暴露"作为搜索策略，是约束满足问题（CSP）里的通用启发式，不止用在数独上。 这是启发式（Heuristic）在回溯中的典型应用：不完备、不保证最优，但凭经验大幅减少搜索空间。数独从"能做出来"走向"跑得快"，靠的就是这类剪枝，具体的算法与启发式的区别可以参考[《启发式方法论》](./12-20-启发式方法论.md)。 ## 回溯问题中的状态管理 这些题目都按决策点展开选择，但状态与约束检测方式不同： | 题目 | 决策点 | 选择列表 | 约束检测 | 解的收集 | |------|--------|----------|----------|----------| | 组合 | 第几个位置 | `start ~ n` | 无 | `res.push` | | 组合求和 | 第几个位置 | 排序后的候选数组 | 剩余目标值 `remain` | `res.push` | | N 皇后 | 第几行 | `0 ~ n-1` 列 | 列 + 对角线 Set | `res.push` | | 数独 | 哪个空格 | `1 ~ 9` | 行 + 列 + 宫 | 原地修改，`boolean` 信号 | 实现时需要检查以下几点： 1. **决策点决定循环结构**：先定位决策点（空格/位置/行），再遍历选择项；决策点永远是外层循环，选择项永远在内层展开。 2. **状态修改与撤销必须对称**：进入递归前 push，返回后必须 pop；数独是赋值，返回后必须恢复为 `.`；Set 是 add，返回后必须 delete。 3. **返回类型取决于解的数量**：收集所有解时使用 `void` 和全局 `res`；只需一个解时用 `boolean` 表示是否已找到解。返回 `true` 后直接沿调用栈返回，不再撤销当前解的状态。 4. **剪枝减少无效搜索**：排序后的 `break`、用 `Set` 记录约束、MRV 优先处理候选项较少的格子，都会更早终止无法得到解的分支。 数独中递归树的分层直接对应循环嵌套顺序：`for (num)` 必须位于定位空格的 `for (r, c)` 内部，才能保证每次递归只处理一个格子。