罗罗编程学习记录
本页内容 展开查看

02.6.2.3 棋盘与 N 皇后数独

所属:全栈开发面试题库 / 02 数据结构与算法 / 02.6 回溯与递归 / 02.6.2 经典回溯题型

02.6.2.3-001 N 皇后(LC 51)怎么逐行回溯?

一句话结论

每行放一个皇后,逐行递归;列、主对角线、副对角线三个标记数组 O(1) 判断冲突;合法位置落子,递归下一行,返回后擦除棋子与标记;行号到 n 收集棋盘。

概念解释

  • 约束:不同列、不同两条对角线。
  • 逐行:每行恰好一个,减少一层枚举。

原理流程

  1. 当前行遍历列。
  2. 冲突则跳过,否则置标记落子。
  3. 递归下一行,返回撤销。

代码 / 示例

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;省掉棋盘拷贝,空间仍为标记数组;可把结果收集换成计数器。

概念解释

  • 计数:只统计合法布局数。
  • 省输出:不存棋盘。

原理流程

  1. 同 51 的冲突判断与落子。
  2. 填满行计数。
  3. 撤销继续枚举。

代码 / 示例

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 恒定。

原理流程

  1. 列下标 c。
  2. 主对角 r-c+n 非负。
  3. 副对角 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 可为负。
  • 平移:整体偏移到下标域。

原理流程

  1. 求 r-c 取值范围。
  2. 加 n 平移。
  3. 同对角线编号一致。

代码 / 示例

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。

概念解释

  • 网格路径:相邻格子。
  • 防重入:路径上标记访问。

原理流程

  1. 枚举起点匹配首字母。
  2. 标记当前格,四方向递归。
  3. 失败撤销标记继续。

代码 / 示例

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 数组。

概念解释

  • 回溯型:路径复用,撤销。
  • 连通型:访问过即永久标记。

原理流程

  1. 判断是否需要回到该格。
  2. 回溯型置位递归后复位。
  3. 连通型标记后不恢复。

代码 / 示例

// 回溯:标记 → 递归 → 复位
// 连通:标记后不再复位

常见误区

  • 误区:连通块题也撤销标记;正解:会重复访问同一连通块。
  • 误区:回溯题不撤销;正解:其他分支无法再走该格。

追问

  • Q:原地改字符有什么好处? A:省 visited 数组空间。
  • Q:恢复时用什么值? A:保存进入前原值。

02.6.2.3-007 解数独(LC 37)怎么回溯?

一句话结论

逐格填空,枚举 1~9 中行列宫均合法的数字,落子递归下一个空格;全部填满返回;失败撤销换数字;配合候选约束剪枝。

概念解释

  • 约束:行、列、3×3 宫不重复。
  • 空格:待填位置。

原理流程

  1. 找下一个空格。
  2. 枚举合法数字。
  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. 统计行列宫占用。
  2. 求空格候选。
  3. 候选最少优先递归。

代码 / 示例

候选 = 1..9 - 行已用 - 列已用 - 宫已用

常见误区

  • 误区:固定按格顺序填;正解:候选最少优先能显著剪枝。
  • 误区:候选计算未排除宫内重复;正解:三处占用都要减。

追问

  • Q:约束传播是什么? A:填一个数后更新相关格候选,继续排除。
  • Q:候选为空说明什么? A:当前分支无解,回溯。

02.6.2.3-009 数独有效性校验(LC 36)与求解有何区别?

一句话结论

校验只检查已填数字在行、列、宫中是否重复,不填空格;求解是回溯枚举空格;校验用集合/位掩码逐行逐列逐宫扫描,O(81)。

概念解释

  • 校验:无重复即可,不要求可解。
  • 求解:补全合法盘面。

原理流程

  1. 扫描每行/列/宫。
  2. 已填数字查重。
  3. 重复即非法。

代码 / 示例

// 行、列、宫各用布尔数组或掩码记录出现数字

常见误区

  • 误区:校验要求盘面可解;正解:只查现有数字冲突。
  • 误区:宫坐标换算错误;正解:宫 (i/3)*3 + j/3。

追问

  • Q:掩码怎么记数字? A:位 1~9 对应 bit,查重用位与。
  • Q:空格在校验中处理吗? A:跳过,只查已填。

02.6.2.3-010 棋盘放棋子类约束回溯怎么抽象?

一句话结论

通用框架:逐行/逐格枚举放置位置,按题目约束(同行同列不重复、对角线、相邻规则)判断合法,放置后递归,返回撤销;约束判断封装成独立函数。

概念解释

  • 通用:位置枚举 + 约束校验。
  • 封装:valid 函数集中规则。

原理流程

  1. 定遍历顺序(行优先)。
  2. valid 判断当前放置是否冲突。
  3. 放置递归撤销。

代码 / 示例

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 个解;对称剪枝需确认题目要全部解还是计数。

概念解释

  • 对称变换:镜像、旋转得到等价布局。
  • 代表解:对称类中的一个。

原理流程

  1. 识别对称方向。
  2. 固定代表位置。
  3. 计数按对称倍数还原。

代码 / 示例

8 皇后:92 个解(含对称)

常见误区

  • 误区:对称剪枝后忘记乘回倍数;正解:计数要还原对称解。
  • 误区:不对称约束也套用;正解:先确认变换保持合法。

追问

  • Q:N=1 有几个解? A:1 个。
  • Q:N=2、3 有解吗? A:无解。

02.6.2.3-012 棋盘状态位运算标记怎么用?

一句话结论

列、对角线占用各用一个整数掩码,位 1 表示占用;冲突判断用位与,落子置位用或,撤销用与非;省去布尔数组,判断 O(1) 且状态紧凑。

概念解释

  • 掩码:整数位集合。
  • 位运算:与判断、或置位、清位。

原理流程

  1. 占用位记录在掩码。
  2. 冲突 (mask & bit) != 0。
  3. 落子 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 皇后均可受益。

概念解释

  • 约束强度:可放置位置多少。
  • 顺序优化:少候选先搜。

原理流程

  1. 估算各位置候选数。
  2. 少候选优先展开。
  3. 冲突分支提前剔除。

代码 / 示例

数独:候选最少空格优先;N 皇后:按行顺序即可

常见误区

  • 误区:搜索顺序影响正确性;正解:只影响效率与剪枝早晚。
  • 误区:为优化顺序打乱约束判断;正解:valid 规则不变。

追问

  • Q:怎么衡量候选多少? A:统计合法可放位置/数字数。
  • Q:最坏复杂度与顺序有关吗? A:最坏仍按满分支,优化改善平均表现。

02.6.2.3-014 单词搜索 II(LC 212)为什么配合字典树?

一句话结论

多单词在同一网格搜索,逐个单词回溯会重复扫描网格;把所有单词插入 Trie,一次 DFS 沿 Trie 前缀扩展,走到单词节点即收集,避免重复遍历前缀。

概念解释

  • Trie:公共前缀共享。
  • 网格 DFS:沿字典树分支走。

原理流程

  1. 单词建 Trie。
  2. 网格起点沿 Trie 递归。
  3. 命中单词节点收集并标记防重复。

代码 / 示例

// Trie 节点存单词结束标记;DFS 中 child = node.children[ch]

常见误区

  • 误区:对每个单词单独跑 LC 79;正解:公共前缀合并到 Trie。
  • 误区:命中单词后不停止 Trie 分支;正解:可能有更长单词,继续向下。

追问

  • Q:复杂度? A:网格起点 × Trie 深度,优于逐单词重复扫描。
  • Q:重复单词怎么去重? A:节点记录已收集或用 Set。

02.6.2.3-015 路径上为什么不能重复访问格子?

一句话结论

题目通常要求路径不自交,重复入格会形成环或重复使用同一位置;当前路径用标记禁止重入,回溯返回后撤销以便其他路径使用;是否允许重复访问按题意。

概念解释

  • 自交:路径回到已走格子。
  • 标记:路径内占用。

原理流程

  1. 进入格子标记。
  2. 路径内不再选该格。
  3. 离开撤销。

代码 / 示例

if (visited[i][j]) continue;

常见误区

  • 误区:所有网格题都禁止重入;正解:最短路径类按题意,可重复则另说。
  • 误区:标记不撤销;正解:兄弟分支需要该格。

追问

  • Q:不禁止重入会怎样? A:路径成环,可能无限递归或非法解。
  • Q:状态可重复到达时怎么办? A:布局记忆化,而非单格 visited。

02.6.2.3-016 棋盘边界检查怎么写?

一句话结论

递归入口先判断行列是否在 [0,m)、[0,n) 内,越界直接返回;再检查当前格子字符/占用;四方向偏移量统一用方向数组遍历。

概念解释

  • 越界:行列超出网格。
  • 方向数组:上下左右偏移。

原理流程

  1. 入口越界判断。
  2. 合法再查内容。
  3. 四方向递归。

代码 / 示例

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 棋盘回溯怎么恢复棋盘字符?

一句话结论

落子前保存原值(空格为 .),递归返回后写回原值;棋子、占用标记、字符三处现场同步撤销;收集棋盘时复制当前盘面。

概念解释

  • 现场:棋子字符 + 标记数组。
  • 恢复:逐项还原。

原理流程

  1. 保存/置位。
  2. 递归。
  3. 字符复位、标记清位。

代码 / 示例

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),输出空间按解数单列。

概念解释

  • 分支:每行/每格候选数。
  • 深度:棋盘规模或单词长度。

原理流程

  1. 估分支因子与深度。
  2. 乘单解构造代价。
  3. 标记与输出空间分开报。

代码 / 示例

N 皇后:O(n!);单词搜索:O(mn·3ᵏ);辅助 O(n²)

常见误区

  • 误区:只报棋盘大小 O(n²);正解:枚举分支才是主要量级。
  • 误区:忽略剪枝说明;正解:先报最坏,再讲约束剪枝收益。

追问

  • Q:数独固定 9×9 复杂度怎么谈? A:按空格数与候选数估分支。
  • Q:棋盘结果拷贝代价? A:每解 O(n²)。

02.6.2.3-019 行优先与逐格枚举怎么选?

一句话结论

每行固定一个棋子的题(N 皇后)按行递归,行内枚举列;每格独立填数的题(数独)逐空格推进;选哪种取决于约束是“每行一个”还是“每格填值”。

概念解释

  • 行优先:行内选列。
  • 逐格:空格顺序填值。

原理流程

  1. 看约束粒度。
  2. 一行一个 → 行递归。
  3. 格格填值 → 逐格递归。

代码 / 示例

N 皇后:solve(row);数独:找下一个空格

常见误区

  • 误区:N 皇后逐格枚举;正解:每行一个,行递归已足够。
  • 误区:数独按行放棋子;正解:每格填数字。

追问

  • Q:行优先减少了哪层? A:省去“放哪一行”的选择。
  • Q:逐格怎么找下一个? A:扫描空格位置。

02.6.2.3-020 棋盘类题目怎么调试与构造用例?

一句话结论

先用最小棋盘(1×1、2×2)验证合法/无解分支,再用典型用例;打印当前棋盘与标记数组对照冲突;重点覆盖越界、重复字符、无解与多解场景。

概念解释

  • 小用例:快速定位逻辑。
  • 对照:棋盘与标记一致。

原理流程

  1. 最小棋盘跑通框架。
  2. 打印落子与撤销。
  3. 补无解、多解、边界用例。

代码 / 示例

用例:N=1 有解;N=2 无解;单词搜索含首字母多起点

常见误区

  • 误区:直接上大棋盘调试;正解:先最小用例走通分支。
  • 误区:只测有解用例;正解:无解路径也要验证回溯正确。

追问

  • Q:棋盘残留棋子怎么查? A:递归前后对比标记与字符。
  • Q:多解怎么核对完整性? A:与已知解数对照(如 8 皇后 92)。