52. N 皇后 II

鲁迅曾说过，有过 N 皇后的经验后，这道题就是纯粹的送分题了，因为题目的

核心解法是完全一样的，只不过这道题目只需要返回方案的个数而已。上一道题

要求返回的是具体的方案，换句话说，只需要在上一道题目的基础上稍作修改即

可。

题意

n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相

互攻击。

可以参考上一题：051.N 皇后

给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。

难度

困难

示例

示例 1：

052.N 皇后 II-20241108085456.png

输入：n = 4

输出：2

解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1

输出：1

分析 1

在 051.N 皇后 中，我们已经将递归+回溯讲得很清楚了，如果理解了 051. N 皇后，这道

题目只能算是一个弱化版本，因为我们已经把方案求解出来了，这道题只需要返回方案的

个数即可。

只需要简单改几个地方，先来看题解。

class Solution {

// 记录解的数量

int solutions = 0;

// 解决 N 皇后问题

public int totalNQueens(int n) {

// 初始化棋盘

char[][] board = new char[n][n];

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

board[i][j] = '.';

}

}

// 开始递归查找所有解

backtrack(board, 0, n);

return solutions;

}

// 回溯方法

private void backtrack(char[][] board, int row, int n) {

// 如果已成功放置完所有皇后，将当前棋盘方案加入 solutions

if (row == n) {

solutions = solutions + 1;

return;

}

// 尝试在当前行的每一列放置皇后

for (int col = 0; col < n; col++) {

// 检查当前位置是否安全

if (isValid(board, row, col, n)) {

// 放置皇后

board[row][col] = 'Q';

// 递归处理下一行

backtrack(board, row + 1, n);

// 回溯，撤销当前放置

board[row][col] = '.';

}

}

}

// 检查在 (row, col) 位置放置皇后是否安全

private boolean isValid(char[][] board, int row, int col, int n) {

// 检查列上是否有皇后

 for (int i = 0; i < row; i++) {

if (board[i][col] == 'Q') {

return false;

}

}

// 检查左上方对角线上是否有皇后

for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {

if (board[i][j] == 'Q') {

return false;

}

}

// 检查右上方对角线上是否有皇后

for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {

if (board[i][j] == 'Q') {

return false;

}

}

return true;

}

}

第一处改动，将 solutions 作为全局变量，用于记录解的数量：

int solutions = 0;

第二处改动，backtrack 回溯方法在找到解的时候将 solutions 加 1 即可：

if (row == n) {

solutions = solutions + 1;

return;

}

第三处改动，删掉 construct 方法，不需要再将当前棋盘状态转换为字符串列表。

回溯和递归的核心框架是不变的，来看题解效率：

052.N 皇后 II-20241108091309.png

分析 2

当然我们还可以稍微做一些变动，通过三个一维数组来记录列、主对角线和副对角线的占

用情况：

• cols：记录哪些列上已有皇后。

• diag1：记录主对角线的状态，主对角线的索引为 row - col + n - 1。

• diag2：记录副对角线的状态，副对角线的索引为 row + col。

052.N 皇后 II-20241108091900.png

①、主对角线：从左上到右下方向，例如 (0,0) -> (1,1) -> (2,2) -> …。在同一主对角线上

的位置 (row, col) 满足 row - col 相等。

也就是说：

• (0, 0): row - col = 0

• (1, 1): row - col = 0

• (2, 2): row - col = 0

主对角线上的元素都满足 row - col = 常数。所以，如果两个位置 (row1, col1) 和 (row2,

col2) 满足 row1 - col1 == row2 - col2，它们就在同一个主对角线上。

对于一个 n x n 的棋盘，row - col 的最小值是 -(n - 1)，最大值是 n - 1。

为了便于将这些值转换成数组索引（0 到 2n - 2），我们可以加上 n - 1 的偏移量。因此：

主对角线的数组索引：row - col + (n - 1)

再比如说：

• (0, 1): row - col = -1

• (1, 2): row - col = -1

• (2, 3): row - col = -1

它们仨都在同一主对角线上，负数没办法做索引，所以我们加上偏移量。

052.N 皇后 II-20241108094800.png

②、副对角线：从右上到左下方向，例如 (0,3) -> (1,2) -> (2,1) -> …。在同一副对角线上

的位置 (row, col) 满足 row + col 相等。

比如说：

• (0, 1): row + col = 1

• (1, 0): row + col = 1

它们俩处在同一副对角线上。

052.N 皇后 II-20241108095602.png

也就是说，当我们放一个皇后的时候，对其所在的列、两条对角线分别进行标记，看看是

否满足不能互相攻击的条件。

来看题解：

class Solution05202 {

// 返回 N 皇后问题的解的数量

public int totalNQueens(int n) {

// 初始化列、主对角线、副对角线的布尔数组

boolean[] cols = new boolean[n]; // 列

boolean[] diag1 = new boolean[2 * n - 1]; // 主对角线

boolean[] diag2 = new boolean[2 * n - 1]; // 副对角线

// 使用递归回溯来计数

return backtrack(0, n, cols, diag1, diag2);

}

// 回溯，返回从当前行开始的解的数量

private int backtrack(int row, int n, boolean[] cols, boolean[] diag1, boolean[]

diag2) {

// 如果所有行都放置完毕，说明找到一种有效解，返回 1

if (row == n) {

return 1;

}

 int solutions = 0; // 记录解的数量

// 遍历当前行的每一列，尝试放置皇后

for (int col = 0; col < n; col++) {

// 计算当前列、主对角线、副对角线的索引

int d1 = row - col + n - 1; // 主对角线索引

int d2 = row + col; // 副对角线索引

// 检查当前位置是否被占用

if (cols[col] || diag1[d1] || diag2[d2]) {

continue; // 如果当前列或对角线被占用，跳过该位置

}

// 放置皇后，标记当前列和对角线已被占用

cols[col] = true;

diag1[d1] = true;

diag2[d2] = true;

// 递归处理下一行，并累加解的数量

solutions += backtrack(row + 1, n, cols, diag1, diag2);

// 回溯，撤销当前皇后位置的占用状态

cols[col] = false;

diag1[d1] = false;

diag2[d2] = false;

}

return solutions; // 返回当前分支的解的数量

}

public static void main(String[] args) {

Solution05202 solution = new Solution05202();

System.out.println(solution.totalNQueens(4)); // 输出: 2

}

}

效率还不错，beat 100%：

052.N 皇后 II-20241108095504.png

总结

LeetCode 上面有很多系列的题目都是同一个套路，也就是说只要你会了其中一个，就可

以以不变应万变。重点是，你能够把其中的一道题目吃“透”，然后以这道题目为突破点，

把整个系列的题目都“举一反三”掉。

力扣链接：https://leetcode.cn/problems/n-queens-ii/