02.6.2.3 棋盘与 N 皇后数独
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.6 回溯与递归 / 02.6.2 经典回溯题型
02.6.2.3-001 N 皇后(LC 51)怎么逐行回溯?
一句话结论
每行放一个皇后,逐行递归;列、主对角线、副对角线三个标记数组 O(1) 判断冲突;合法位置落子,递归下一行,返回后擦除棋子与标记;行号到 n 收集棋盘。
概念解释
- 约束:不同列、不同两条对角线。
- 逐行:每行恰好一个,减少一层枚举。
原理流程
- 当前行遍历列。
- 冲突则跳过,否则置标记落子。
- 递归下一行,返回撤销。
代码 / 示例
void solve(int row, int n, boolean[] col, boolean[] d1, boolean[] d2,
char[][] board, List<List<String>> res) {
if (row == n) { res.add(build(board)); return; }
for (int c = 0; c < n; c++) {
int id1 = row - c + n, id2 = row + c;
if (col[c] || d1[id1] || d2[id2]) continue;
col[c] = d1[id1] = d2[id2] = true;
board[row][c] = 'Q';
solve(row + 1, n, col, d1, d2, board, res);
board[row][c] = '.';
col[c] = d1[id1] = d2[id2] = false;
}
}
常见误区
- 误区:判断冲突只看列;正解:两条对角线都要判。
- 误区:返回后忘记擦除棋盘;正解:棋子与三个标记都要撤销。
追问
- Q:复杂度? A:最坏 O(n!) 量级,剪枝后远低;棋盘收集 O(n²)。
- Q:为什么逐行而不是逐格? A:每行一个皇后,行内枚举列即可。
02.6.2.3-002 N 皇后 II(LC 52)只求计数怎么做?
一句话结论
与 LC 51 同框架,到达行 n 时不构造棋盘,直接计数 +1;省掉棋盘拷贝,空间仍为标记数组;可把结果收集换成计数器。
概念解释
- 计数:只统计合法布局数。
- 省输出:不存棋盘。
原理流程
- 同 51 的冲突判断与落子。
- 填满行计数。
- 撤销继续枚举。
代码 / 示例
if (row == n) { count++; return; }
常见误区
- 误区:计数题还存全部棋盘;正解:只累加整数省空间。
- 误区:计数器忘记回溯复位;正解:计数在叶子累加,不涉及撤销。
追问
- Q:8 皇后有多少解? A:92 个。
- Q:计数能用记忆化吗? A:占用布局是状态,规模小可掩码缓存。
02.6.2.3-003 列与两条对角线冲突怎么标记?
一句话结论
列用长度 n 数组;主对角线(左上到右下)row-col 平移 +n 作下标,副对角线(右上到左下)row+col 作下标;三个布尔数组置位/复位。
概念解释
- 主对角:
r-c恒定。 - 副对角:
r+c恒定。
原理流程
- 列下标 c。
- 主对角
r-c+n非负。 - 副对角
r+c。
代码 / 示例
int d1 = row - col + n; // 主对角线
int d2 = row + col; // 副对角线
常见误区
- 误区:
r-c直接作下标出现负数;正解:平移 +n。 - 误区:两条对角线用错下标;正解:恒定值分别是差与和。
追问
- Q:对角线数组长度? A:主对角 2n-1,副对角 2n-1。
- Q:能用一个整数掩码代替吗? A:可以,位运算分别记录三类占用。
02.6.2.3-004 为什么主对角线编号要 row-col+n?
一句话结论
row-col 范围是 -(n-1) ~ n-1,直接作数组下标为负越界;平移 +n 后落到 0 ~ 2n-2 的非负区间,保证同一主对角线下标恒定且合法。
概念解释
- 负值:r-c 可为负。
- 平移:整体偏移到下标域。
原理流程
- 求 r-c 取值范围。
- 加 n 平移。
- 同对角线编号一致。
代码 / 示例
n=4:r-c ∈ [-3,3],+4 → [1,7]
常见误区
- 误区:平移量写错;正解:加 n 使最小值到 0。
- 误区:副对角也平移;正解:r+c 非负,无需平移。
追问
- Q:副对角下标范围? A:0 ~ 2n-2。
- Q:平移后还能区分两条对角吗? A:用两个独立数组分别记录。
02.6.2.3-005 单词搜索(LC 79)网格回溯怎么写?
一句话结论
在网格上从每个起点 DFS,匹配单词首字母;访问过的格子临时标记,沿四方向匹配下一字符,递归返回恢复;匹配完整单词返回 true。
概念解释
- 网格路径:相邻格子。
- 防重入:路径上标记访问。
原理流程
- 枚举起点匹配首字母。
- 标记当前格,四方向递归。
- 失败撤销标记继续。
代码 / 示例
boolean dfs(char[][] b, int i, int j, String w, int k) {
if (k == w.length()) return true;
if (i < 0 || j < 0 || i >= b.length || j >= b[0].length || b[i][j] != w.charAt(k)) return false;
char old = b[i][j]; b[i][j] = '#';
for (int[] d : DIRS)
if (dfs(b, i + d[0], j + d[1], w, k + 1)) return true;
b[i][j] = old;
return false;
}
常见误区
- 误区:路径走过的格子可重复走;正解:同一路径不能重入,需标记撤销。
- 误区:恢复字符写错;正解:保存原值再还原。
追问
- Q:复杂度? A:最坏 O(mn·3ᵏ),k 为单词长度。
- Q:四个方向顺序影响正确性吗? A:不影响,只影响剪枝早晚。
02.6.2.3-006 网格 visited 标记与撤销怎么管理?
一句话结论
回溯型网格(单词搜索)路径上格子用完需撤销,供其他分支再走;连通块型网格(岛屿数量)标记后不撤销;标记可用原地改字符或独立 visited 数组。
概念解释
- 回溯型:路径复用,撤销。
- 连通型:访问过即永久标记。
原理流程
- 判断是否需要回到该格。
- 回溯型置位递归后复位。
- 连通型标记后不恢复。
代码 / 示例
// 回溯:标记 → 递归 → 复位
// 连通:标记后不再复位
常见误区
- 误区:连通块题也撤销标记;正解:会重复访问同一连通块。
- 误区:回溯题不撤销;正解:其他分支无法再走该格。
追问
- Q:原地改字符有什么好处? A:省 visited 数组空间。
- Q:恢复时用什么值? A:保存进入前原值。
02.6.2.3-007 解数独(LC 37)怎么回溯?
一句话结论
逐格填空,枚举 1~9 中行列宫均合法的数字,落子递归下一个空格;全部填满返回;失败撤销换数字;配合候选约束剪枝。
概念解释
- 约束:行、列、3×3 宫不重复。
- 空格:待填位置。
原理流程
- 找下一个空格。
- 枚举合法数字。
- 填入递归,失败擦除。
代码 / 示例
boolean solve(char[][] b) {
for (int i = 0; i < 9; i++) for (int j = 0; j < 9; j++)
if (b[i][j] == '.') {
for (char c = '1'; c <= '9'; c++) {
if (valid(b, i, j, c)) {
b[i][j] = c;
if (solve(b)) return true;
b[i][j] = '.';
}
}
return false;
}
return true;
}
常见误区
- 误区:合法性只检查行;正解:行列宫三处都要查。
- 误区:找到一解不停止;正解:数独求一解,成功即逐层返回。
追问
- Q:复杂度? A:指数级,受空格数与候选约束影响。
- Q:怎么加速? A:优先填候选最少的格子,约束传播。
02.6.2.3-008 数独候选与剪枝怎么做?
一句话结论
为每个空格预计算行列宫已用数字,候选为剩余可填值;优先填候选数最少的格子,缩小分支;冲突数字直接排除,避免无效递归。
概念解释
- 候选集:当前可填数字。
- 最少候选优先:约束最强的位置先填。
原理流程
- 统计行列宫占用。
- 求空格候选。
- 候选最少优先递归。
代码 / 示例
候选 = 1..9 - 行已用 - 列已用 - 宫已用
常见误区
- 误区:固定按格顺序填;正解:候选最少优先能显著剪枝。
- 误区:候选计算未排除宫内重复;正解:三处占用都要减。
追问
- Q:约束传播是什么? A:填一个数后更新相关格候选,继续排除。
- Q:候选为空说明什么? A:当前分支无解,回溯。
02.6.2.3-009 数独有效性校验(LC 36)与求解有何区别?
一句话结论
校验只检查已填数字在行、列、宫中是否重复,不填空格;求解是回溯枚举空格;校验用集合/位掩码逐行逐列逐宫扫描,O(81)。
概念解释
- 校验:无重复即可,不要求可解。
- 求解:补全合法盘面。
原理流程
- 扫描每行/列/宫。
- 已填数字查重。
- 重复即非法。
代码 / 示例
// 行、列、宫各用布尔数组或掩码记录出现数字
常见误区
- 误区:校验要求盘面可解;正解:只查现有数字冲突。
- 误区:宫坐标换算错误;正解:宫
(i/3)*3 + j/3。
追问
- Q:掩码怎么记数字? A:位 1~9 对应 bit,查重用位与。
- Q:空格在校验中处理吗? A:跳过,只查已填。
02.6.2.3-010 棋盘放棋子类约束回溯怎么抽象?
一句话结论
通用框架:逐行/逐格枚举放置位置,按题目约束(同行同列不重复、对角线、相邻规则)判断合法,放置后递归,返回撤销;约束判断封装成独立函数。
概念解释
- 通用:位置枚举 + 约束校验。
- 封装:valid 函数集中规则。
原理流程
- 定遍历顺序(行优先)。
- valid 判断当前放置是否冲突。
- 放置递归撤销。
代码 / 示例
if (valid(board, r, c)) { place(r,c); dfs(...); remove(r,c); }
常见误区
- 误区:约束散落在递归各处;正解:集中到 valid 便于核对。
- 误区:放置标记不撤销;正解:兄弟分支需要空位。
追问
- Q:马/车类约束区别? A:各自 valid 规则不同,框架一致。
- Q:多棋子类型怎么办? A:状态记录各类占用。
02.6.2.3-011 N 皇后解数与对称性怎么理解?
一句话结论
N 皇后解具有左右镜像、旋转对称;计数时可利用对称只搜代表布局再换算;8 皇后共 92 个解;对称剪枝需确认题目要全部解还是计数。
概念解释
- 对称变换:镜像、旋转得到等价布局。
- 代表解:对称类中的一个。
原理流程
- 识别对称方向。
- 固定代表位置。
- 计数按对称倍数还原。
代码 / 示例
8 皇后:92 个解(含对称)
常见误区
- 误区:对称剪枝后忘记乘回倍数;正解:计数要还原对称解。
- 误区:不对称约束也套用;正解:先确认变换保持合法。
追问
- Q:N=1 有几个解? A:1 个。
- Q:N=2、3 有解吗? A:无解。
02.6.2.3-012 棋盘状态位运算标记怎么用?
一句话结论
列、对角线占用各用一个整数掩码,位 1 表示占用;冲突判断用位与,落子置位用或,撤销用与非;省去布尔数组,判断 O(1) 且状态紧凑。
概念解释
- 掩码:整数位集合。
- 位运算:与判断、或置位、清位。
原理流程
- 占用位记录在掩码。
- 冲突
(mask & bit) != 0。 - 落子
mask | bit,撤销mask & ~bit。
代码 / 示例
int bit = 1 << c;
if ((col & bit) != 0) continue;
col |= bit; dfs(...); col &= ~bit;
常见误区
- 误区:撤销用异或;正解:与非更安全,避免重复翻转。
- 误区:掩码位数不足;正解:n 位以内,注意整数宽度。
追问
- Q:位掩码适合 N 皇后吗? A:适合,列与两对角线各一掩码。
- Q:n 超过整数位宽怎么办? A:用大数或回布尔数组。
02.6.2.3-013 棋盘回溯的搜索顺序怎么优化?
一句话结论
优先枚举约束强、候选少的位置(如候选最少空格),分支更早被剪;落子顺序不影响合法解集合,只影响找到解的速度;数独、N 皇后均可受益。
概念解释
- 约束强度:可放置位置多少。
- 顺序优化:少候选先搜。
原理流程
- 估算各位置候选数。
- 少候选优先展开。
- 冲突分支提前剔除。
代码 / 示例
数独:候选最少空格优先;N 皇后:按行顺序即可
常见误区
- 误区:搜索顺序影响正确性;正解:只影响效率与剪枝早晚。
- 误区:为优化顺序打乱约束判断;正解:valid 规则不变。
追问
- Q:怎么衡量候选多少? A:统计合法可放位置/数字数。
- Q:最坏复杂度与顺序有关吗? A:最坏仍按满分支,优化改善平均表现。
02.6.2.3-014 单词搜索 II(LC 212)为什么配合字典树?
一句话结论
多单词在同一网格搜索,逐个单词回溯会重复扫描网格;把所有单词插入 Trie,一次 DFS 沿 Trie 前缀扩展,走到单词节点即收集,避免重复遍历前缀。
概念解释
- Trie:公共前缀共享。
- 网格 DFS:沿字典树分支走。
原理流程
- 单词建 Trie。
- 网格起点沿 Trie 递归。
- 命中单词节点收集并标记防重复。
代码 / 示例
// Trie 节点存单词结束标记;DFS 中 child = node.children[ch]
常见误区
- 误区:对每个单词单独跑 LC 79;正解:公共前缀合并到 Trie。
- 误区:命中单词后不停止 Trie 分支;正解:可能有更长单词,继续向下。
追问
- Q:复杂度? A:网格起点 × Trie 深度,优于逐单词重复扫描。
- Q:重复单词怎么去重? A:节点记录已收集或用 Set。
02.6.2.3-015 路径上为什么不能重复访问格子?
一句话结论
题目通常要求路径不自交,重复入格会形成环或重复使用同一位置;当前路径用标记禁止重入,回溯返回后撤销以便其他路径使用;是否允许重复访问按题意。
概念解释
- 自交:路径回到已走格子。
- 标记:路径内占用。
原理流程
- 进入格子标记。
- 路径内不再选该格。
- 离开撤销。
代码 / 示例
if (visited[i][j]) continue;
常见误区
- 误区:所有网格题都禁止重入;正解:最短路径类按题意,可重复则另说。
- 误区:标记不撤销;正解:兄弟分支需要该格。
追问
- Q:不禁止重入会怎样? A:路径成环,可能无限递归或非法解。
- Q:状态可重复到达时怎么办? A:布局记忆化,而非单格 visited。
02.6.2.3-016 棋盘边界检查怎么写?
一句话结论
递归入口先判断行列是否在 [0,m)、[0,n) 内,越界直接返回;再检查当前格子字符/占用;四方向偏移量统一用方向数组遍历。
概念解释
- 越界:行列超出网格。
- 方向数组:上下左右偏移。
原理流程
- 入口越界判断。
- 合法再查内容。
- 四方向递归。
代码 / 示例
int[][] DIRS = {{-1,0},{1,0},{0,-1},{0,1}};
if (i < 0 || i >= m || j < 0 || j >= n) return;
常见误区
- 误区:先访问格子再判越界;正解:先越界判断避免数组下标异常。
- 误区:方向只写两个;正解:四方向齐全。
追问
- Q:网格是环形边界吗? A:普通题不环绕,越界即停。
- Q:越界返回什么? A:按题意 false 或空。
02.6.2.3-017 棋盘回溯怎么恢复棋盘字符?
一句话结论
落子前保存原值(空格为 .),递归返回后写回原值;棋子、占用标记、字符三处现场同步撤销;收集棋盘时复制当前盘面。
概念解释
- 现场:棋子字符 + 标记数组。
- 恢复:逐项还原。
原理流程
- 保存/置位。
- 递归。
- 字符复位、标记清位。
代码 / 示例
char old = board[i][j]; board[i][j] = 'Q';
dfs(...);
board[i][j] = old;
常见误区
- 误区:只擦棋子不清标记;正解:占用数组也要复位。
- 误区:恢复成固定
.;正解:应保存原值,兼容预填格。
追问
- Q:结果棋盘怎么拷贝? A:逐行复制 char 数组。
- Q:恢复顺序有要求吗? A:与置位逆序即可。
02.6.2.3-018 棋盘题复杂度口径怎么报?
一句话结论
最坏按满决策树估:N 皇后 O(n!) 量级,单词搜索 O(mn·3ᵏ),数独随空格数指数级;辅助空间为棋盘/标记 O(n²) 或 O(mn),输出空间按解数单列。
概念解释
- 分支:每行/每格候选数。
- 深度:棋盘规模或单词长度。
原理流程
- 估分支因子与深度。
- 乘单解构造代价。
- 标记与输出空间分开报。
代码 / 示例
N 皇后:O(n!);单词搜索:O(mn·3ᵏ);辅助 O(n²)
常见误区
- 误区:只报棋盘大小 O(n²);正解:枚举分支才是主要量级。
- 误区:忽略剪枝说明;正解:先报最坏,再讲约束剪枝收益。
追问
- Q:数独固定 9×9 复杂度怎么谈? A:按空格数与候选数估分支。
- Q:棋盘结果拷贝代价? A:每解 O(n²)。
02.6.2.3-019 行优先与逐格枚举怎么选?
一句话结论
每行固定一个棋子的题(N 皇后)按行递归,行内枚举列;每格独立填数的题(数独)逐空格推进;选哪种取决于约束是“每行一个”还是“每格填值”。
概念解释
- 行优先:行内选列。
- 逐格:空格顺序填值。
原理流程
- 看约束粒度。
- 一行一个 → 行递归。
- 格格填值 → 逐格递归。
代码 / 示例
N 皇后:solve(row);数独:找下一个空格
常见误区
- 误区:N 皇后逐格枚举;正解:每行一个,行递归已足够。
- 误区:数独按行放棋子;正解:每格填数字。
追问
- Q:行优先减少了哪层? A:省去“放哪一行”的选择。
- Q:逐格怎么找下一个? A:扫描空格位置。
02.6.2.3-020 棋盘类题目怎么调试与构造用例?
一句话结论
先用最小棋盘(1×1、2×2)验证合法/无解分支,再用典型用例;打印当前棋盘与标记数组对照冲突;重点覆盖越界、重复字符、无解与多解场景。
概念解释
- 小用例:快速定位逻辑。
- 对照:棋盘与标记一致。
原理流程
- 最小棋盘跑通框架。
- 打印落子与撤销。
- 补无解、多解、边界用例。
代码 / 示例
用例:N=1 有解;N=2 无解;单词搜索含首字母多起点
常见误区
- 误区:直接上大棋盘调试;正解:先最小用例走通分支。
- 误区:只测有解用例;正解:无解路径也要验证回溯正确。
追问
- Q:棋盘残留棋子怎么查? A:递归前后对比标记与字符。
- Q:多解怎么核对完整性? A:与已知解数对照(如 8 皇后 92)。