企业官网建设流程全解析

我最早在递归问题上栽跟头，不是栽在“递归不下去”，而是栽在“递归回来了却忘了擦脚印”。那时候写八皇后，递归一层层往下钻很顺利，一回头，状态数组里还留着上一次尝试的痕迹，于是后面的分支全都莫名其妙地“继承”了脏数据。后来我才意识到，回溯算法真正要练的从来不是往深走，而是怎么干净地回来。

八皇后、N皇后，再到力扣（LeetCode）第51题和第52题，基本就是同一条线：从经典问题建立回溯思维，用剪枝把搜索空间压下去，最后落到真实题目上写出能AC的代码。这篇文章我会从八皇后的本质开始拆，把回溯的三步套路、冲突检测的数学规律、三层剪枝方案、以及51和52两题的完整写法都过一遍。刚学数据结构的人可以从头跟到尾，准备面试的人可以直接跳到第4章和第5章，把模板拿去背。

1. 八皇后问题的本质：为什么它一直是回溯课的“头号例题”

1.1 问题定义与“互不攻击”的三条约束

八皇后问题是经典的国际象棋背景题：在一个8×8的棋盘上放置8个皇后，要求任意两个皇后不能互相攻击。皇后在国际象棋里能横向、纵向、沿45度对角线无限延伸攻击，所以三个硬性约束就是：

• 不能同一行
• 不能同一列
• 不能在任意一条45度斜线上

这个限制条件看起来不多，但如果你试图“硬想”出所有摆法，几乎不可能。事实上，8×8棋盘上合法摆法有92种，而光是从8行每行选一列，就有8的8次方也就是1677万多个组合。真正难得不是“放得下”，而是在庞大的组合空间里系统性地找出所有合法方案，并且不重不漏。

这也是为什么回溯类课程几乎都拿八皇后当开场题。它的约束非常直观，棋盘是二维的，坐标关系一眼能看懂，但它的搜索空间又不是小到可以暴力枚举，必须引入“走不通就回头”的思维。换句话说，八皇后是理解回溯和剪枝的最短路径。

1.2 回溯和暴力枚举的本质区别

暴力的做法很直接：枚举所有可能的摆放组合，最后再统一检查每一条45度斜线是否冲突。问题是，这种做法的计算量完全不可控。哪怕只是N=10，行和列的组合已经有100亿种，验证工作根本做不完。

回溯的做法是在“每放一个皇后”的时候就立刻检查。它的推进思路是：先放第一行的皇后，再放第二行的皇后，每放一步都保证当前这枚皇后和之前的不冲突，然后继续往下走。如果你放到某一行时发现，这一行的全部8列都已经和前面放好的皇后冲突，那就说明之前的某一步选择是错的，必须回到上一行，换一个位置重新尝试。

这个过程用生活类比就是走迷宫。你在每一个岔路口选一条路走进去，如果前面是死胡同，你原路退回到上一个岔路口，换一条路继续试。但有个关键动作：回去的时候一定要把沿途做的标记擦掉，否则下一个分支进来的时候，看到的全是上一个分支留下的记号，那个迷宫就彻底没法走了。

所以回溯的本质可以理解为“深度优先搜索 + 状态回退”。它专门用来解决约束满足问题，比如排列、组合、子集、数独、N皇后。这类问题有一个共同特点：要找的是所有合法解，而不是一个最优解。

1.3 为什么从八皇后到N皇后不是重复劳动

八皇后写出来以后，很多人觉得这就是一道老古董题，换个数字而已。但LeetCode 51和52恰恰是把8换成了n：第51题要求返回所有N皇后的棋盘布局，第52题要求返回合法方案的数量。两道题看起来只差一个“输出棋盘”和“输出数量”，但真到实现层面，存储、剪枝、对称性处理的复杂度会差很多，这也是我后面要展开的重点。

从八皇后到N皇后，本质上是从“背答案”变成“写泛化代码”。8皇后你可能手工都能摆出几个布局，但是n=12、n=13之后，手工就彻底无能为力，必须靠递归程序去搜索。而这个代码能不能从8平滑扩展到任意n，就考验你回溯框架是不是真的理解了。

2. 回溯三件套：选择、递归、撤销，先写一个能跑的版本

2.1 一套通用回溯框架

先给出一套我用了很久的回溯模板。不管是排列、组合还是N皇后，本质上都是在套这个架子：

void backtrack(路径, 可选列表) { if (满足结束条件) { 记录结果; return; } for (选择 : 可选列表) { 做选择; backtrack(新的路径, 新的可选列表); 撤销选择; } }

这套架子一共就四个位置要填：结束条件、扩展开局、递归入口、恢复现场。难点从来不是框架本身，而是怎么把具体问题的“选择”和“撤销”真正理解透。

对于N皇后来说，“路径”是已经放置的皇后坐标，“可选列表”是当前行还能放哪些列。“做选择”是把当前行某一列标记为已占用，“撤销选择”就是在递归返回后把标记去掉。如果去掉这步，整个回溯就退化成了一次没完没了的深度优先搜索，结果要么错误，要么栈溢出。

2.2 八皇后的最简实现：数组下标天然完成撤销

先写一个最简单的版本。用int[] cols来记录每一行的皇后放在哪一列，一行一个皇后，行冲突天然不存在，所以只需要检查列冲突：

int count = 0; public int totalNQueensWithOnlyColCheck(int n) { int[] cols = new int[n]; // cols[行] = 列 dfs(n, 0, cols); return count; } private void dfs(int n, int row, int[] cols) { if (row == n) { count++; return; } for (int col = 0; col < n; col++) { if (!isValid(row, col, cols)) { continue; } cols[row] = col; dfs(n, row + 1, cols); // cols[row] 不需要显式清空，因为后续分支会覆盖 } } private boolean isValid(int row, int col, int[] cols) { for (int i = 0; i < row; i++) { if (cols[i] == col) { return false; } // 对角线判断先空着，后面补 } return true; }

这个版本只能处理列冲突，答案肯定是错的，但适合用来观察一个现象：这里的“撤销”是隐式的。递归回到上一层之后，cols[row]的旧值并没有手动清除，但下一次循环会直接重新赋值，所以旧值自然被覆盖掉了。很多初学者看到代码里没有撤销步骤，就以为回溯可以不用恢复现场，这是一个特别危险的误解。

这个写法能省略撤销，是因为cols是一个普通数组，我们只需要检查下标小于row的行，更后面的行就算残留旧值也不影响。可一旦换成boolean数组、集合、多个标记数组同时使用的时候，就不能这么偷懒了。

2.3 显式状态数组：为什么必须恢复现场

真正标准的做法是用boolean数组显式记录状态，并且每一层递归结束时显式恢复：

private void dfs(int n, int row, boolean[] colUsed, boolean[] diag1, boolean[] diag2, List<List<String>> res, int[] cols) { if (row == n) { res.add(buildBoard(cols, n)); return; } for (int col = 0; col < n; col++) { int d1 = row + col; int d2 = row - col + n - 1; if (colUsed[col] || diag1[d1] || diag2[d2]) { continue; } cols[row] = col; colUsed[col] = true; diag1[d1] = true; diag2[d2] = true; dfs(n, row + 1, colUsed, diag1, diag2, res, cols); colUsed[col] = false; diag1[d1] = false; diag2[d2] = false; } }

这里的撤销逻辑非常清晰：我在这一层做了哪些标记，递归返回后就把哪些标记逐一取消。如果不恢复，比如在某一行选择了第3列并标记diag1[某下标]为true，递归回来后不撤销，那么下一次循环换第5列尝试时，第5列可能明明不冲突，却被一个已经废弃的旧标记挡住，整个分支就白白少了一条路。

我见过太多人在这步翻车。递归函数本身会用栈自动保存局部变量，但boolean数组、List、int[]这些都是引用类型，所有递归分支共享同一份内存。你不能指望系统帮你回滚这些外部状态，只能自己手动擦脚印。

3. 冲突检测的三种方案：列标记、对角线数学规律、坐标偏移

3.1 同一列的判断：boolean数组标记是O(1)

如果只用int[] cols记录每行的列坐标，那么判断“当前行的第col列是否冲突”的办法是遍历之前的所有行，看看有没有一行也选了第col列。这个做法的时间复杂度是O(row)，随着递归深度增加会越来越慢。

更好的方案是用一个boolean[] colUsed，长度正好是n。放置皇后的时候把colUsed[col]置为true，撤销时改回false，判断冲突时就只需要读一次数组，变成O(1)操作。空间占用是O(n)，完全可以接受。

3.2 斜线冲突的数学本质：坐标差恒定与坐标和恒定

对角线冲突是最容易写错的部分。先推导一下背后的数学规律：

如果两个皇后分别放在坐标(i, j)和(k, l)，它们在同一条“左上到右下”的斜线上时，满足i - j = k - l。也就是说，主对角线上所有格子的行减列是同一个常数。

如果它们在“右上到左下”的斜线上，则满足i + j = k + l。也就是说，副对角线上所有格子的行加列是同一个常数。

既然行减列的取值区间是[-(n-1), n-1]，行加列的取值区间是[0, 2n-2]，那两条对角线一共就有2n-1种取值。所以两个对角线标记数组的长度都应该是2*n-1，而不是n。这个细节我至少见人写错过五次以上。

行减列可能是负数，比如下标0减去下标7等于-7。Java的数组下标不能是负数，所以需要整体偏移n-1，把范围平移到[0, 2n-2]。行加列本身就是非负整数，不需要偏移。

看一组坐标示意：假设n=8，皇后放在第2行第3列，即(2, 3)。那么：

• 它在主对角线方向上影响所有满足row - col = -1的格子
• 它在副对角线方向上影响所有满足row + col = 5的格子
• 数组下标分别是-1 + 8 - 1 = 6，以及5

于是代码里的d1和d2就是：

int d1 = row + col; // 副对角线，右上到左下 int d2 = row - col + n - 1; // 主对角线，左上到右下

这里提醒一个容易搞混的口诀：写棋盘题时，脑子里面把“主对角线”和“副对角线”的定义固定下来。我习惯把“左上到右下”叫主对角线（\），把“右上到左下”叫副对角线（/）。你只要自己统一，别写到一半换定义就行。

3.3 三种检测策略的对比

我的建议是先把第二种方案吃透，再把第三种当成进阶优化。位运算写起来非常飘逸，但如果没理解数学坐标关系，你很难读懂为什么要把状态左移和右移。

4. 剪枝的三个层次：从“能跑”到“快到能算到N=14”

4.1 剪枝的第一性原理：回溯树的每条边都是一次尝试

先把复杂度摆出来。如果完全不检测冲突，只按逐行放置来看，每行都有n种选择，状态空间是n的n次方。加入列冲突限制之后，因为每列只能选一次，本质上就是n个列的排列组合，规模降到n!。但n!增长速度依然惊人，10的阶乘已经是3628800，13的阶乘更是超过62亿。如果没有额外的剪枝，N皇后到n=10就已经很难受了。

剪枝做的事情很简单：把那些注定不可能通向合法解的分支，在早期直接掐掉。回到程序上，就是在递归进入下一层之前，尽量把当前选择是否“有前途”判断出来。这里的“前途”不只是当前这一步不冲突，还包括这一步留下的标记已经堵死了某些后续路径。

4.2 第一层剪枝：放置前就用isValid断冲突

最基础也最关键的剪枝，是在“做选择”之前先检查冲突，而不是先递归进去再判断。看代码就能发现，if (colUsed[col] || diag1[d1] || diag2[d2]) continue;这一行就是一个强剪枝。它把当前行全部8列里不满足条件的列直接跳过，根本不会进入更深层的递归。

如果反过来，把判断放在递归函数的最开头，也能得到正确结果，但那些“放了就冲突”的节点依然会膨胀出无数个无效子节点。放到N=12的时候，两者运行时间会差出数量级。这类剪枝有个很形象的说法：不要等到迷宫深处才发现死路，而是在岔路口就排除明显走不通的方向。

4.3 第二层剪枝：利用棋盘对称性，适合计数场景

N皇后问题有一个很漂亮的性质：如果一个解是合法的，那么它沿着棋盘垂直中轴镜像翻转之后，依然是合法解。用坐标表示就是，第一行第c列的皇后，翻转到第一行第n-1-c列。

这意味着第一行皇后放在左半区间的每一组解，都会在右半区间存在一一对应的镜像解。于是搜索时只需要枚举第一行的左半部分列的方案，最后把数量乘以2，就能得到全部解。伪代码如下：

// 伪代码：对称剪枝 for LeetCode 52 count = 0; for (int c = 0; c < n / 2; c++) { count += dfsStartWithFirstRowCol(c); } count *= 2; if (n % 2 == 1) { count += dfsStartWithFirstRowCol(n / 2); }

奇数n的时候有个大坑。如果n是奇数，棋盘中间那一列翻转后还是它自己，不是和右半列成对出现。所以第一行放在中间列的解不能直接翻倍，必须单独跑一次DFS，把中间列的方案数原样加到总数里。我见过有人在n=9时忘了这个特殊处理，结果答案差了整整一倍。

对称剪枝是典型的“收益大、坑也大”的优化。它适合第52题这种只要数量的场景，但不适合第51题，因为第51题要求输出所有棋盘，如果只搜索左半边再靠镜像生成右半边解，实现复杂度会高很多，得不偿失。

4.4 第三层剪枝：位运算状态压缩

位运算剪枝是把三个boolean数组换成三个整数，用二进制位的0和1表示状态。这样做的好处有三个：状态拷贝更快、判断冲突更快、递归参数传递更轻。

先说原理。用一个整数cols记录哪些列已经被皇后占据，二进制位第i位为1表示第i列已占用；再用一个整数d1记录主对角线被占据的情况，d2记录副对角线被占据的情况。那么在某一行的可用位置就是：

int available = ((1 << n) - 1) & ~(cols | d1 | d2);

这个式子先构造出n个低位全是1的mask，然后把三种占据状态的并集取反，剩下的1就是还没有被攻击的列。

取最低位的1可以用pos = available & (-available)，拿掉最低位的1可以用available &= available - 1。这两个位运算小技巧是高效遍历所有可选位置的经典操作。具体到递归传参时，列状态直接继承，主对角线状态整体左移一位，副对角线状态整体右移一位，因为下一行比当前行行号大1，斜线影响范围自然会顺着棋盘方向移动一格。

5. LeetCode 51与52实战：解集构造和方案计数走的是两条路

5.1 51的完整Java实现与棋盘构造细节

第51题要求返回所有解，每个解是一个List ，每行字符串里放一个Q，其余位置是点。核心代码我在前面已经拆过状态数组的部分，这里给出完整可运行的版本：

class Solution { public List<List<String>> solveNQueens(int n) { List<List<String>> res = new ArrayList<>(); int[] cols = new int[n]; // cols[row] = 皇后所在的列 boolean[] colUsed = new boolean[n]; boolean[] diag1 = new boolean[2 * n - 1]; // row + col boolean[] diag2 = new boolean[2 * n - 1]; // row - col + n - 1 dfs(n, 0, cols, colUsed, diag1, diag2, res); return res; } private void dfs(int n, int row, int[] cols, boolean[] colUsed, boolean[] diag1, boolean[] diag2, List<List<String>> res) { if (row == n) { res.add(buildBoard(cols, n)); return; } for (int col = 0; col < n; col++) { int d1 = row + col; int d2 = row - col + n - 1; if (colUsed[col] || diag1[d1] || diag2[d2]) { continue; } cols[row] = col; colUsed[col] = true; diag1[d1] = true; diag2[d2] = true; dfs(n, row + 1, cols, colUsed, diag1, diag2, res); colUsed[col] = false; diag1[d1] = false; diag2[d2] = false; } } private List<String> buildBoard(int[] cols, int n) { List<String> board = new ArrayList<>(); for (int r = 0; r < n; r++) { char[] line = new char[n]; Arrays.fill(line, '.'); line[cols[r]] = 'Q'; board.add(new String(line)); } return board; } }

注意buildBoard里的char[]是新创建的，每次构造棋盘时互不影响，不需要恢复。真正需要在递归里恢复的只有三个状态数组。还有一个小细节：到达叶子节点时，res.add的是buildBoard返回的新List，而不是某个复用对象，否则所有结果会指向同一份被不断修改的棋盘。

5.2 52的数组版实现：只计数，省掉棋盘

第52题不需要返回棋盘，只要方案数量。代码几乎就是把51里的结果列表换成一个计数器：

class Solution { private int count = 0; public int totalNQueens(int n) { boolean[] colUsed = new boolean[n]; boolean[] diag1 = new boolean[2 * n - 1]; boolean[] diag2 = new boolean[2 * n - 1]; dfs(n, 0, colUsed, diag1, diag2); return count; } private void dfs(int n, int row, boolean[] colUsed, boolean[] diag1, boolean[] diag2) { if (row == n) { count++; return; } for (int col = 0; col < n; col++) { int d1 = row + col; int d2 = row - col + n - 1; if (colUsed[col] || diag1[d1] || diag2[d2]) { continue; } colUsed[col] = true; diag1[d1] = true; diag2[d2] = true; dfs(n, row + 1, colUsed, diag1, diag2); colUsed[col] = false; diag1[d1] = false; diag2[d2] = false; } } }

这个版本空间复杂度是O(n)，递归深度是n，非常稳定。如果n比较小比如8或9，运行起来和位运算版本几乎没有差别，但代码可读性高很多。面试的时候我通常建议先写这个版本，至少保证思路完整、逻辑清晰。

5.3 位运算版52的完整实现与实测

再给一版用位运算的极致写法：

class Solution { public int totalNQueens(int n) { return dfs(n, 0, 0, 0, 0); } private int dfs(int n, int row, int cols, int d1, int d2) { if (row == n) { return 1; } int count = 0; int available = ((1 << n) - 1) & ~(cols | d1 | d2); while (available != 0) { int pos = available & (-available); // 取最低位的1 count += dfs(n, row + 1, cols | pos, (d1 | pos) << 1, (d2 | pos) >> 1); available &= available - 1; // 去掉最低位的1 } return count; } }

递归参数里，cols表示当前列占用状态；d1表示主对角线状态，每深入一行整体左移一位；d2表示副对角线状态，每深入一行整体右移一位。这个移动方向必须想清楚：主对角线影响范围会随着行号增加而向左移动，副对角线则向右移动。

我在本地用同一环境跑过数组版和位运算版。n=10时两者差距不明显，n=12开始位运算版本明显更快，n=13时大致能快出近一倍。数据会随机器不同有波动，但趋势是一致的。所以我的建议是：先用数组版把题做对，AC之后再考虑位运算优化，不要一上来就上硬货。

N皇后的解数增长很快：n=8是92，n=9是352，n=10是724，n=11是2680，n=12是14200，n=13是73712，n=14是365596。当你n来到14，数组版遍历到的节点数已经非常可观，剪枝好不好一眼就能看出来。

5.4 容易踩的几个坑

第一个坑：对角线数组长度写错。不管是diag1还是diag2，长度必须是2*n-1。写着写着顺手写成了n，下标就会越界。

第二个坑：row - col取到负数时忘了偏移。主对角线数组下标要写成row - col + n - 1，别直接用row - col。

第三个坑：位运算里忘了限制二进制位范围。available计算时如果不和((1 << n) - 1)做与运算，d1左移之后可能把高位溢出到第n位以上，导致结果少算。

第四个坑：对称剪枝在奇数n下把中间列的解也翻倍了。处理办法是中间列单独统计，不乘2。

第五个坑：51题的棋盘恢复问题。有些写法是递归过程中直接修改char[][] board，这一层改成Q，递归返回后又改回点。这个思路没问题，但一定记得改回去，不然下一分支会看到残留的Q。

学习回溯的正确顺序

我个人的建议是：先不要碰LeetCode 52的位运算解法，也不要搞对称剪枝。先用一个数组版的八皇后代码，亲手跑通n=8，把“做选择、递归、撤销”三个动作的位置烂熟于心。然后把n改成12，用肉眼感受一下剪枝前后运行时间的差异。等你能把下面这五个问题瞬间答上来，再去优化也不迟：

1. 为什么八皇后不需要检测行冲突？
2. 主对角线数组为什么用row - col恒定的规律？
3. 为什么回溯递归回来之后必须恢复boolean数组？
4. 位运算版本中d1为什么要左移，d2为什么要右移？
5. LeetCode 51和52除了返回值之外，在剪枝策略上哪里不同？

把这道题彻底吃透，往后刷数独、复原IP地址、括号生成、全排列这些回溯题，其实都是在同一个架子上换零件。所谓剪枝，也不过是提前把没希望的分支砍掉，让递归这棵决策树长得更“瘦”一些。你自己动手把N皇后从8跑到12，再回头看第51题和第52题，就会觉得它们真的只是同一道题换了两件外衣。