1. 什么是 N 皇后问题？
N 皇后问题是计算机科学中的经典问题，也是学习回溯算法的必修课。
题目要求将 个皇后放置在 的棋盘上，使得任意两个皇后都不能互相攻击。
在国际象棋中，皇后可以沿行、列和两条对角线方向攻击，因此任何两个皇后都不能处于同一行、同一列或同一条对角线上。
2. 核心思路：回溯算法
因为我们需要找到所有可能的解，而每一步都面临多种选择，一旦发现当前选择导致后面无法放置，就需要撤销选择、回到上一步尝试其他位置。这种”不断尝试，不行就退回”的思想就是回溯算法。
算法的基本步骤如下：
- 从第 行开始，逐行放置皇后。
- 在当前行中，遍历每一列，检查在位置 放置皇后是否合法。
- 如果合法，放置皇后并标记该列、两条对角线已被占用，然后递归处理下一行。
- 当所有行都处理完毕，就找到了一个合法方案，将其记录下来。
- 递归返回后，撤销当前位置的占用状态，尝试当前行的下一列。
回溯的核心口诀做出选择 递归探索下一层 撤销选择（恢复现场）。
3. 如何判断位置是否合法？
在 的棋盘上，最直观的方法是每次都遍历检查当前位置的同一列和两条对角线是否有其他皇后，但这会耗时较高。
为了将判断的时间复杂度降为 ，我们可以使用布尔数组来记录已被占用的列和对角线。
在棋盘坐标系 中，三种冲突的数学特征如下：
- 同一列： 的值相同。
- 主对角线（↘方向）：同一条对角线上的所有点， 的值相同。
- 副对角线（↙方向）：同一条对角线上的所有点， 的值相同。
以 的棋盘为例：
- 主对角线：、、 处于同一条主对角线，它们的 都等于 。
- 副对角线：、、 处于同一条副对角线，它们的 都等于 。
3.1 对角线数组的下标映射
由于数组下标不能为负数，我们需要对计算结果进行处理：
- 主对角线（）：取值范围是 到 。统一加上 后，映射为 ，取值范围变为 到 。
- 副对角线（）：取值范围已经是 到 ，可以直接用作数组下标。
因此，diagonals1 和 diagonals2 数组的长度都是 。
NOTE通过三个布尔数组
cols、diagonals1和diagonals2，就能在 的时间内判断某个位置是否可以放置皇后。
4. 以 n = 4 为例走一遍流程
以 为例，用 ASCII 棋盘展示回溯的完整搜索过程。Q 表示皇后，. 表示空位。
第 0 行，在 放置：
Q . . .. . . .. . . .. . . .第 1 行， 冲突（同列）， 冲突（主对角线）， 合法，放置：
Q . . .. . Q .. . . .. . . .第 2 行， 冲突（副对角线）， 冲突（同列）， 冲突（同列）， 冲突（主对角线）。四列全部冲突，无法放置，回溯。
撤销第 1 行 ，尝试 ，合法，放置：
Q . . .. . . Q. . . .. . . .第 2 行， 冲突（同列）， 合法，放置：
Q . . .. . . Q. Q . .. . . .第 3 行，四列全部冲突，无法放置，回溯。
撤销第 2 行 ，无更多列可尝试，继续回溯。撤销第 1 行 ，无更多列可尝试，继续回溯。
第 0 行，撤销 ，尝试 ，合法，放置：
. Q . .. . . .. . . .. . . .沿这条分支继续搜索，最终找到一个合法解：
. Q . .. . . QQ . . .. . Q .即 [.Q.., ...Q, Q..., ..Q.]。整个搜索过程就是在状态树上做深度优先遍历，走不通就回头换路。 时共有 个解。
5. Java 实现
import java.util.ArrayList;import java.util.Arrays;import java.util.List;
class Solution { List<List<String>> res = new ArrayList<>();
public List<List<String>> solveNQueens(int n) { // 棋盘初始化，全填充为 '.' char[][] board = new char[n][n]; for (char[] row : board) { Arrays.fill(row, '.'); }
// 记录列和两条对角线是否被占用 boolean[] cols = new boolean[n]; boolean[] diagonals1 = new boolean[2 * n - 1]; // 主对角线 row - col + n - 1 boolean[] diagonals2 = new boolean[2 * n - 1]; // 副对角线 row + col
backtrack(board, 0, n, cols, diagonals1, diagonals2); return res; }
private void backtrack(char[][] board, int row, int n, boolean[] cols, boolean[] diagonals1, boolean[] diagonals2) { // 所有行都已放置完毕，找到一个合法解 if (row == n) { res.add(generateBoard(board)); return; }
// 遍历当前行的每一列，尝试放置皇后 for (int col = 0; col < n; col++) { int diag1 = row - col + n - 1; int diag2 = row + col;
// 如果该位置的列或对角线已被占用，跳过 if (cols[col] || diagonals1[diag1] || diagonals2[diag2]) { continue; }
// 做出选择：放置皇后，更新占用状态 board[row][col] = 'Q'; cols[col] = true; diagonals1[diag1] = true; diagonals2[diag2] = true;
// 递归进入下一行 backtrack(board, row + 1, n, cols, diagonals1, diagonals2);
// 撤销选择：恢复棋盘和占用状态 board[row][col] = '.'; cols[col] = false; diagonals1[diag1] = false; diagonals2[diag2] = false; } }
// 将字符数组转为题目要求的 List<String> 格式 private List<String> generateBoard(char[][] board) { List<String> list = new ArrayList<>(); for (char[] row : board) { list.add(new String(row)); } return list; }}6. 复杂度分析
- 时间复杂度：。
- 空间复杂度：。递归调用栈深度为 ，三个布尔数组
cols、diagonals1和diagonals2的长度均为 。
时间复杂度为什么是 而不是 ？表面上看，回溯函数里只有一个 for 循环遍历 列，似乎每层只做 的工作。但实际上，dfs(0) 调用 dfs(1)，dfs(1) 调用 dfs(2)，形成了一棵搜索树：
dfs(0) ├── dfs(1) │ ├── dfs(2) │ │ ├── dfs(3) │ │ └── ... │ └── ... └── ...第 0 层有 个分支，第 1 层每个节点最多 个分支（已用掉一列），第 2 层最多 个分支，以此类推。搜索树的叶子节点数量上界为 。实际搜索中由于对角线冲突的剪枝，状态树远小于 ，但最坏情况下仍为 。
8. 总结
N 皇后问题的核心是：
按行放置，逐列尝试；利用数组记录冲突，通过回溯不断试错。
如果这篇文章对你有帮助，欢迎分享给更多人！
部分信息可能已经过时