052. N皇后II
作者：沉默王二
发布时间：2024-11-08T10:01:54.756+0800
鲁迅曾说过，有过 N 皇后的经验后，这道题就是纯粹的送分题了，因为题目的核心解法是完全一样的，只不过这道题目只需要返回方案的个数而已。上一道题要求返回的是具体的方案，换句话说，只需要在上一道题目的基础上稍作修改即可。
题意
n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。
可以参考上一题：051.N 皇后
给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。
难度
困难
示例
示例 1：
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
输入：n = 4
输出：2
解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
输入：n = 1
输出：1
### 分析 1
在051.N皇后 中，我们已经将递归+回溯讲得很清楚了，如果理解了 051. N 皇后，这道题目只能算是一个弱化版本，因为我们已经把方案求解出来了，这道题只需要返回方案的个数即可。
只需要简单改几个地方，先来看题解。
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
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 作为全局变量，用于记录解的数量：
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
int solutions = 0;
第二处改动，backtrack 回溯方法在找到解的时候将 solutions 加 1 即可：
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
if (row == n) {
solutions = solutions + 1;
return;
}
第三处改动，删掉 construct 方法，不需要再将当前棋盘状态转换为字符串列表。
回溯和递归的核心框架是不变的，来看题解效率：
分析 2
当然我们还可以稍微做一些变动，通过三个一维数组来记录列、主对角线和副对角线的占用情况：
cols：记录哪些列上已有皇后。
diag1：记录主对角线的状态，主对角线的索引为 row - col + n - 1。
diag2：记录副对角线的状态，副对角线的索引为 row + col。
①、主对角线：从左上到右下方向，例如 (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
它们仨都在同一主对角线上，负数没办法做索引，所以我们加上偏移量。
②、副对角线：从右上到左下方向，例如 (0,3) -> (1,2) -> (2,1) -> ...。在同一副对角线上的位置 (row, col) 满足 row + col 相等。
比如说：
(0, 1): row + col = 1
(1, 0): row + col = 1
它们俩处在同一副对角线上。
也就是说，当我们放一个皇后的时候，对其所在的列、两条对角线分别进行标记，看看是否满足不能互相攻击的条件。
来看题解：
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
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%：
总结
LeetCode 上面有很多系列的题目都是同一个套路，也就是说只要你会了其中一个，就可以以不变应万变。重点是，你能够把其中的一道题目吃“透”，然后以这道题目为突破点，把整个系列的题目都“举一反三”掉。
力扣链接：https://leetcode.cn/problems/n-queens-ii/
一步一个脚印
不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。
PDF 版本目前只针对二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 加入我们吧。
一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 6500 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！
语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu
这道题可以说完全重写了，给出 2 道大家完全都能掌握的题解（主要是递归和回溯，判断条件略有不同）。
增加代码注释，这样大家更容易看懂并掌握题解；
增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；
增加手绘图，这样大家更容易理解解题思路；
增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；
增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；
图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。
另外，这一版本会作为 PDF 的终稿随后在星球进行发布。