企业官网建设流程全解析

• 示例工程

本文以 solution/0000-0099/0051.N-Queens/README.md 为核心，系统讲解 LeetCode 51. N 皇后问题：从题目规则、回溯思路推导，到三个 O(1) 标记数组的设计，再到 Python、Java、C++、Go、TypeScript、C# 六种语言的同构实现与逐行剖析。读完你不仅能独立写出 N 皇后解法，还能把"按行放置 + 标记数组剪枝"这套回溯模板迁移到数独、全排列、组合等同类搜索问题中。

题目速览：N 皇后问题是什么

按照国际象棋的规则，皇后可以攻击与之处在同一行、同一列或同一斜线上的棋子。n 皇后问题研究的是如何将n个皇后放置在n×n的棋盘上，并且使皇后彼此之间不能相互攻击。

给定一个整数n，题目要求返回所有不同的 n 皇后问题解决方案。每一种解法包含一个不同的棋子放置方案，其中'Q'代表皇后，'.'代表空位。

示例 1：

输入：n = 4 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] 解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1 输出：[["Q"]]

提示：1 <= n <= 9。

该题在 LeetCode 上的难度为困难（Hard），仓库中的标签标注为「数组」「回溯」「X 算法」，其中「X 算法」是指该问题还可以建模为精确覆盖（Exact Cover）后用 Algorithm X 求解的另一条路线，本文主体采用官方文档给出的 DFS 回溯解法。仓库同时提供英文版题解供对照阅读。

思路分析：为什么选择逐行回溯而非全排列暴力

拿到题目后，最直觉的思路是枚举列的全排列：把第i行的皇后放在第p_i列，然后整体检查对角线是否冲突。这个方案的搜索上界是n!，而n <= 9时9! = 362880理论上可以搜完。

但问题在于：

1. 冲突发现得太晚。全排列方案要等整盘棋子全部放完才做一次完整校验，而实际上冲突往往在放置中途就已经出现，中途发现却无法及时剪枝，浪费大量搜索；
2. 棋盘字符串只能在叶子节点构造。每到达一个排列终点才逐行拼接字符串，无法边放边维护棋盘状态。

关键洞察在于：每行恰好只能放一个皇后，所以一旦确定"按行放"，冲突就只可能来自两种维度：

• 同一列：两皇后落在同一列j；
• 同一对角线：两皇后落在同一条正对角线或反对角线上。

而"同一对角线"有一个极其优美的数学特征：对棋盘上任意位置(i, j)，

• 落在同一条正对角线（从左上到右下）上的所有格子，其i + j是同一个常数；
• 落在同一条反对角线（从右上到左下）上的所有格子，其n - i + j是同一个常数。

因此，同一列、同一正对角线、同一反对角线，都可以用数组下标在 O(1) 时间内查询与更新，完全不需要每次去扫描整行整列或遍历对角线。这正是文档思考部分的核心推导："一行恰好一个皇后之后，冲突只可能来自同列或同对角线。同一列、同一正对角线 $i+j$、同一反对角线 $n-i+j$ 都可以用数组在 $O(1)$ 时间内查询与更新。"

于是得到最终方案：按行 DFS（深度优先搜索）+ 回溯，只在三个标记均空闲时落子，在棋盘上同步写入'Q'，递归返回时撤销标记恢复'.'。

回溯算法详解：三个标记数组与 O(1) 冲突检测

状态表示

定义三个数组col、dg和udg，分别表示列、正对角线和反对角线上是否已有皇后：

• col[j]：第j列是否被占用；
• dg[i + j]：位置(i, j)所在的正对角线是否被占用；
• udg[n - i + j]：位置(i, j)所在的反对角线是否被占用。

如果位置(i, j)有皇后，那么col[j]、dg[i + j]、udg[n - i + j]都为1。

数组长度上有两个细节值得注意：

• col长度为n（共n列）；
• dg与udg长度为n << 1（即2n）。因为i + j的取值范围是0 ~ 2n-2，n - i + j的取值范围是0 ~ 2n-2，2n的长度恰好覆盖所有可能的下标，避免越界。

另外用二维数组g记录当前棋盘状态，初始时所有元素都是'.'。

递归函数 dfs(i)

定义dfs(i)表示从第i行开始放置皇后，其完整流程为：

1. 终止条件：若i == n，说明全部n个皇后已放置完毕，把当前棋盘g的每一行拼接成字符串后放入答案数组，递归结束；
2. 枚举列：遍历当前行i的每一列j，判断位置(i, j)是否可放皇后，即检查col[j] + dg[i + j] + udg[n - i + j] == 0（三个标记全为0才合法）；
3. 落子并标记：将g[i][j]改为'Q'，并把col[j]、dg[i + j]、udg[n - i + j]全部置为1；
4. 递归深入：调用dfs(i + 1)继续搜索下一行；
5. 回溯撤销：递归返回后，将g[i][j]改回'.'，并把三个标记全部复位为0，以便尝试当前行的下一个列位置。

主函数中调用dfs(0)启动搜索，最后返回答案数组。

三个标记合并写成col[j] + dg[i + j] + udg[n - i + j] == 0，利用"三个 0/1 值之和为 0 当且仅当三者全为 0"的性质，一行代码完成合法性判断，这也是仓库六种语言实现中完全一致的写法。

复杂度分析

文档给出的结论是：时间复杂度O(n² × n!)，空间复杂度O(n)，其中n是题目给定的整数。

• 时间上界按"逐层枚举 + 剪枝"的松弛分析得到：每一层最多枚举n列，配合对角线剪枝后实际搜索量远小于n^n，文档将其上界记为O(n² × n!)（n²来自每层n个分支与最终答案的拼接开销，n!来自列放置排列的上界）；
• 空间上，col/dg/udg三个数组、递归栈深度n以及棋盘g都是O(n)量级。

多语言实现：六种语言的同构代码

仓库在solution/0000-0099/0051.N-Queens/目录下为每个语言提供了独立源码文件：Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.cs。核心逻辑在所有语言中完全一致，下面逐一给出并标注关键差异。

Python3

对应文件 Solution.py：

class Solution: def solveNQueens(self, n: int) -> List[List[str]]: def dfs(i: int): if i == n: ans.append(["".join(row) for row in g]) return for j in range(n): if col[j] + dg[i + j] + udg[n - i + j] == 0: g[i][j] = "Q" col[j] = dg[i + j] = udg[n - i + j] = 1 dfs(i + 1) col[j] = dg[i + j] = udg[n - i + j] = 0 g[i][j] = "." ans = [] g = [["."] * n for _ in range(n)] col = [0] * n dg = [0] * (n << 1) udg = [0] * (n << 1) dfs(0) return ans

要点：Python 版本在叶子节点用"".join(row)把每行字符数组拼成字符串；col[j] = dg[i + j] = udg[n - i + j] = 1的链式赋值一条语句完成三个标记的写入与复位。

Java

对应文件 Solution.java：

class Solution { private List<List<String>> ans = new ArrayList<>(); private int[] col; private int[] dg; private int[] udg; private String[][] g; private int n; public List<List<String>> solveNQueens(int n) { this.n = n; col = new int[n]; dg = new int[n << 1]; udg = new int[n << 1]; g = new String[n][n]; for (int i = 0; i < n; ++i) { Arrays.fill(g[i], "."); } dfs(0); return ans; } private void dfs(int i) { if (i == n) { List<String> t = new ArrayList<>(); for (int j = 0; j < n; ++j) { t.add(String.join("", g[j])); } ans.add(t); return; } for (int j = 0; j < n; ++j) { if (col[j] + dg[i + j] + udg[n - i + j] == 0) { g[i][j] = "Q"; col[j] = dg[i + j] = udg[n - i + j] = 1; dfs(i + 1); col[j] = dg[i + j] = udg[n - i + j] = 0; g[i][j] = "."; } } } }

要点：Java 使用String[][]存储棋盘，叶子节点用String.join("", g[j])逐行拼接；n << 1是位运算左移一位，等价于n * 2，用于快速申请2n长度的对角线数组。

C++

对应文件 Solution.cpp：

class Solution { public: vector<vector<string>> solveNQueens(int n) { vector<int> col(n); vector<int> dg(n << 1); vector<int> udg(n << 1); vector<vector<string>> ans; vector<string> t(n, string(n, '.')); function<void(int)> dfs = & -> void { if (i == n) { ans.push_back(t); return; } for (int j = 0; j < n; ++j) { if (col[j] + dg[i + j] + udg[n - i + j] == 0) { t[i][j] = 'Q'; col[j] = dg[i + j] = udg[n - i + j] = 1; dfs(i + 1); col[j] = dg[i + j] = udg[n - i + j] = 0; t[i][j] = '.'; } } }; dfs(0); return ans; } };

要点：C++ 用vector<string>直接表示棋盘，每行是一个string(n, '.')初始化的字符串，可原地用t[i][j] = 'Q'修改字符；递归用function<void(int)>+ lambda 捕获外部变量实现。

Go

对应文件 Solution.go：

func solveNQueens(n int) (ans [][]string) { col := make([]int, n) dg := make([]int, n<<1) udg := make([]int, n<<1) t := make([][]byte, n) for i := range t { t[i] = make([]byte, n) for j := range t[i] { t[i][j] = '.' } } var dfs func(int) dfs = func(i int) { if i == n { tmp := make([]string, n) for i := range tmp { tmp[i] = string(t[i]) } ans = append(ans, tmp) return } for j := 0; j < n; j++ { if col[j]+dg[i+j]+udg[n-i+j] == 0 { col[j], dg[i+j], udg[n-i+j] = 1, 1, 1 t[i][j] = 'Q' dfs(i + 1) t[i][j] = '.' col[j], dg[i+j], udg[n-i+j] = 0, 0, 0 } } } dfs(0) return }

要点：Go 用[][]byte存棋盘（字节数组便于就地修改），叶子节点用string(t[i])把每行字节数组转换为字符串；ans通过命名返回值直接return。

TypeScript

对应文件 Solution.ts：

function solveNQueens(n: number): string[][] { const col: number[] = Array(n).fill(0); const dg: number[] = Array(n << 1).fill(0); const udg: number[] = Array(n << 1).fill(0); const ans: string[][] = []; const t: string[][] = Array.from({ length: n }, () => Array(n).fill('.')); const dfs = (i: number) => { if (i === n) { ans.push(t.map(x => x.join(''))); return; } for (let j = 0; j < n; ++j) { if (col[j] + dg[i + j] + udg[n - i + j] === 0) { t[i][j] = 'Q'; col[j] = dg[i + j] = udg[n - i + j] = 1; dfs(i + 1); col[j] = dg[i + j] = udg[n - i + j] = 0; t[i][j] = '.'; } } }; dfs(0); return ans; }

要点：TypeScript 与 Java 的棋盘表示一致，叶子节点用t.map(x => x.join(''))一次性完成整盘拼接，代码最简洁。

C#

对应文件 Solution.cs：

public class Solution { private int n; private int[] col; private int[] dg; private int[] udg; private IList<IList<string>> ans = new List<IList<string>>(); private IList<string> t = new List<string>(); public IList<IList<string>> SolveNQueens(int n) { this.n = n; col = new int[n]; dg = new int[n << 1]; udg = new int[n << 1]; dfs(0); return ans; } private void dfs(int i) { if (i == n) { ans.Add(new List<string>(t)); return; } for (int j = 0; j < n; ++j) { if (col[j] + dg[i + j] + udg[n - i + j] == 0) { char[] row = new char[n]; Array.Fill(row, '.'); row[j] = 'Q'; t.Add(new string(row)); col[j] = dg[i + j] = udg[n - i + j] = 1; dfs(i + 1); col[j] = dg[i + j] = udg[n - i + j] = 0; t.RemoveAt(t.Count - 1); } } } }

要点：C# 是六种实现中唯一不预建棋盘的版本——它在每次尝试放置时用char[]现造一行row，t.Add(new string(row))动态加入当前解，回溯时t.RemoveAt(t.Count - 1)移除该行，逻辑与其他语言的"原地修改棋盘"等价但风格不同。

以 n=4 为例：回溯搜索的完整轨迹

我们手工推演一遍dfs在第一组解上的执行路径，验证算法的正确性（行、列下标均从 0 开始）：

1. dfs(0)：(0, 1)处col[1] + dg[1] + udg[3] == 0，落子，棋盘第 0 行变为.Q..，标记col[1]、dg[1]、udg[3]；
2. dfs(1)：逐列检查，j = 3时col[3] + dg[4] + udg[2] == 0，落子，第 1 行变为...Q，标记col[3]、dg[4]、udg[2]；
3. dfs(2)：受前两行标记约束，第 2 行的j = 0是第一个合法列，落子，第 2 行变为Q...；
4. dfs(3)：只剩j = 2可用，落子，第 3 行变为..Q.；
5. dfs(4)：i == n，得到第一组解[".Q..","...Q","Q...","..Q."]并收入答案；
6. 回溯逐层撤销标记，继续在dfs(2)尝试其他列、在dfs(1)尝试其他列……最终找到第二组解["..Q.","Q...","...Q",".Q.."]。

可以观察到：在第 3 步时，若j = 0之外还有候选列，算法会继续尝试；若某行完全无合法列，dfs直接返回，天然形成剪枝——这正是回溯相对全排列暴力的效率优势所在。

仓库中的相关资源与延伸阅读

围绕本主题，仓库提供了完整的可验证资源：

• 核心题解文档：中文版 README 与英文版 README，两份文档保持相同的解法结构与复杂度结论；
• 六种语言源码：Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.cs，可直接对照运行；
• 题目配图：images/queens.jpg展示 n=4 的两种解法，images/8-queens.png为 8 皇后棋盘示意图；
• 同源变体题：lcci/08.12.Eight Queens/README.md（《程序员面试金典》面试题 08.12 八皇后）与本题为同一问题、同一套col/dg/udg回溯解法，并且额外提供了 Swift 实现，可以作为"掌握一种解法、通吃多道题"的佐证。

从解题方法论上看，N 皇后是回溯算法最经典的入门模板，其核心套路——"用哈希/数组记录已占用状态、按序决策、递归深入、回溯撤销"——可直接迁移到数独求解、全排列与组合、括号生成、图着色等大量搜索问题，值得反复手写训练。

调试与实战要点

最后给出几条实用的验证与调试建议：

1. 用最小规模自测：n = 1应返回[["Q"]]，这是最容易手工验证的边界用例；
2. 用 n=4 对照：n = 4应恰好返回 2 组解，与题目示例完全一致，可作为正确性基准；
3. 核对对角线下标范围：dg与udg长度必须是2n（代码里写作n << 1），i + j与n - i + j的最大值都是2n - 2，若误用n长度必然越界；
4. 回溯顺序不能颠倒：标准写法是"先复位标记、再复位棋盘字符"，若顺序颠倒或漏写任一复位操作，都会导致后续分支被错误剪枝或棋盘残留'Q'；
5. 关注状态复位的对称性：对比 Python/Java/C++/TS/Go 与 C# 两种风格可以发现，无论"原地改棋盘"还是"动态增删行"，核心都是保证每次尝试前后的状态完全一致，这是回溯正确性的根本。

掌握了这份解法，你既可以在 LeetCode 51 上 AC，也能直接迁移到面试题 08.12 八皇后等同类问题，真正做到"一题通、类题通"。

• 示例工程