深入解析：LeetCode 51 - N皇后问题 详解笔记
1. 问题概述
1.1 题目描述
n皇后问题研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。
输入：整数 n
输出：所有不同的n皇后问题的解决方案
表示方法：'Q' 表示皇后，'.' 表示空位
1.2 攻击规则
皇后可以攻击同一行、同一列、同一斜线上的任何棋子。因此n皇后问题要求：
- 任意两个皇后不能处于同一行
- 任意两个皇后不能处于同一列
- 任意两个皇后不能处于同一斜线（包括左斜线和右斜线）
1.3 示例
示例 1:
输入: n = 4
输出: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释: 4皇后问题存在两个不同的解法
解法1: 解法2:
. Q . . . . Q .
. . . Q Q . . .
Q . . . . . . Q
. . Q . . Q . .
示例 2:
输入: n = 1
输出: [["Q"]]1.4 约束条件
1 ≤ n ≤ 9
2. 解题思路 - 回溯算法
2.1 核心思想
使用回溯算法逐行放置皇后：
- 从第0行开始，依次在每一行放置一个皇后
- 对于当前行，尝试在每一列放置皇后
- 检查当前位置是否与已放置的皇后冲突
- 如果不冲突，放置皇后并递归处理下一行
- 递归返回后，撤销当前皇后的放置（回溯）
- 当所有行都放置完毕，找到一个解
2.2 为什么逐行放置？
- 自动避免行冲突：每行只放一个皇后，确保不会有两个皇后在同一行
- 降低复杂度：将二维搜索转化为一维搜索，只需考虑列和斜线冲突
3. 冲突检测策略（核心）
3.1 冲突检测数组
使用三个布尔数组实现O(1)时间的冲突检测：
| 数组 | 含义 | 索引计算 | 大小 | 说明 |
|---|---|---|---|---|
ca[n] | 列冲突 | ca[j] | n | ca[j]=true 表示第j列已有皇后 |
cb[2n-1] | 左斜线冲突 | cb[i+j] | 2n-1 | cb[i+j]=true 表示该左斜线已有皇后 |
cc[2n-1] | 右斜线冲突 | cc[n-1-(i-j)] | 2n-1 | cc[n-1-(i-j)]=true 表示该右斜线已有皇后 |
3.2 斜线索引计算详解
3.2.1 左斜线（↘方向）
特点：同一左斜线上的格子，i + j 值为常数
索引计算：index = i + j
范围：[0, 2n-2]（共 2n-1 条左斜线）
n=4时的左斜线索引标注：
j=0 j=1 j=2 j=3
i=0 0 1 2 3
i=1 1 2 3 4
i=2 2 3 4 5
i=3 3 4 5 63.2.2 右斜线（↙方向）
特点：同一右斜线上的格子，i - j 值为常数
索引计算：index = n - 1 - (i - j)
目的：将 i - j 的范围 [-(n-1), n-1] 映射到 [0, 2n-2]
范围：[0, 2n-2]（共 2n-1 条右斜线）
n=4时的右斜线索引标注：
j=0 j=1 j=2 j=3
i=0 3 4 5 6
i=1 2 3 4 5
i=2 1 2 3 4
i=3 0 1 2 34. 算法实现详解
4.1 整体流程
主函数 solveNQueens():
1. 初始化冲突检测数组 ca, cb, cc
2. 初始化棋盘 table（全部填充'.'）
3. 创建结果集 result
4. 调用 dfs(0, ...) 从第0行开始搜索
5. 返回 result
回溯函数 dfs(i, ...):
1. 如果 i == n（所有行处理完）
- 将当前棋盘转换为字符串列表
- 加入result，返回
2. 遍历当前行i的每一列j
- 检查冲突：ca[j] || cb[i+j] || cc[n-1-(i-j)]
- 如果冲突，跳过
- 放置皇后，标记冲突
- 递归处理下一行：dfs(i+1, ...)
- 回溯：撤销皇后，清除冲突标记4.2 关键代码实现
package com.it.X_回溯;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class NQueenLeetcode51 {
public static void main(String[] args) {
System.out.println(solveNQueens(4)); // 4皇后问题
System.out.println(solveNQueens(1)); // 1皇后问题
}
/**
* N皇后问题求解主函数
* @param n 棋盘大小
* @return 所有可行的解决方案
*/
static List<List<String>> solveNQueens(int n) {
// 1. 初始化列冲突检测数组
boolean[] ca = new boolean[n];
// 2. 初始化左斜线冲突检测数组（↘方向）
// 大小为 2n-1，因为 i+j 的范围是 [0, 2n-2]
boolean[] cb = new boolean[2 * n - 1];
// 3. 初始化右斜线冲突检测数组（↙方向）
// 大小为 2n-1，因为 i-j 的范围是 [-(n-1), n-1]
boolean[] cc = new boolean[2 * n - 1];
// 4. 初始化棋盘，全部填充为 '.'（空位）
char[][] table = new char[n][n];
for (char[] chars : table) {
Arrays.fill(chars, '.');
}
// 5. 存储所有解决方案
List<List<String>> result = new ArrayList<>();
// 6. 从第0行开始回溯搜索
dfs(0, n, table, ca, cb, cc, result);
return result;
}
/**
* 深度优先搜索（DFS）回溯函数
* @param i 当前处理的行号（0到n-1）
*/
static void dfs(int i, int n, char[][] table, boolean[] ca,
boolean[] cb, boolean[] cc, List<List<String>> result) {
// 终止条件：所有行都已放置皇后
if (i == n) {
// 将当前棋盘状态转换为字符串列表
List<String> list = new ArrayList<>();
for (char[] chars : table) {
list.add(new String(chars));
}
result.add(list);
return;
}
// 遍历当前行的每一列，尝试放置皇后
for (int j = 0; j < n; j++) {
// ===== 冲突检测 =====
// 1. ca[j]: 第j列是否已有皇后
// 2. cb[i+j]: 该左斜线（↘）是否已有皇后
// 3. cc[n-1-(i-j)]: 该右斜线（↙）是否已有皇后
if (ca[j] || cb[i + j] || cc[n - 1 - (i - j)]) {
continue; // 跳过冲突列
}
// ===== 做选择 =====
table[i][j] = 'Q'; // 放置皇后
ca[j] = cb[i + j] = cc[n - 1 - (i - j)] = true; // 标记冲突
// ===== 递归 =====
dfs(i + 1, n, table, ca, cb, cc, result); // 处理下一行
// ===== 撤销选择（回溯）=====
table[i][j] = '.'; // 移除皇后
ca[j] = cb[i + j] = cc[n - 1 - (i - j)] = false; // 清除冲突标记
}
}
}5. 复杂度分析
5.1 时间复杂度：O(n!)
理论上界为 n!，因为：
- 第1行有
n种选择 - 第2行最多
n-1种选择 - 第3行最多
n-2种选择 - …
- 总共约
n × (n-1) × (n-2) × ... × 1 = n!种可能
5.2 空间复杂度
| 组成部分 | 空间 | 说明 |
|---|---|---|
| 递归调用栈 | O(n) | 最大递归深度为n |
| 冲突检测数组 | O(n) | 三个数组大小分别为n, 2n-1, 2n-1 |
| 棋盘 | O(n²) | n×n的字符数组 |
| 总空间 | O(n²) | 主要由棋盘决定 |
6. 优化技巧
6.1 位运算优化
使用位运算代替布尔数组，可大幅减少空间占用：
- 用一个整数的每一位表示冲突状态
- 利用位运算快速判断和更新状态
- 空间复杂度可从O(n)降至O(1)
6.2 对称性剪枝
- n皇后问题的解具有对称性
- 只搜索一半的解，然后通过对称变换得到另一半
- 可减少约50%的搜索空间
6.3 启发式搜索
- 优先选择约束最多的位置（可放置皇后最少的行）
- 减少回溯次数，提高效率
7. 相关问题推荐
| 问题编号 | 问题名称 | 关联度 | 说明 |
|---|---|---|---|
| LeetCode 52 | N皇后 II | ★★★★★ | 只求解的数量，不需输出具体方案 |
| LeetCode 37 | 解数独 | ★★★★☆ | 二维回溯问题，约束更复杂 |
| LeetCode 980 | 不同路径 III | ★★★☆☆ | 回溯+路径搜索，状态管理类似 |
8. 总结
8.1 核心要点
- 逐行放置：自动避免行冲突，降低问题复杂度
- 三数组检测：使用
ca,cb,cc实现O(1)冲突检测 - 斜线索引：理解
i+j和n-1-(i-j)的映射关系是关键 - 回溯思想：递归+状态恢复，枚举所有可能解
浙公网安备 33010602011771号