当前位置：首页 > news >正文

深入解析：LeetCode 51 - N皇后问题详解笔记

news 2026/5/12 17:39:02

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行开始，依次在每一行放置一个皇后
对于当前行，尝试在每一列放置皇后
检查当前位置是否与已放置的皇后冲突
如果不冲突，放置皇后并递归处理下一行
递归返回后，撤销当前皇后的放置（回溯）
当所有行都放置完毕，找到一个解

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    6

3.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    3

4. 算法实现详解

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	★★★☆☆	回溯+路径搜索，状态管理类似