N 皇后 II
难度:
标签:
题目描述
n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。
示例 1：
输入：n = 4 输出：2 解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：
输入：n = 1 输出：1
提示：
1 <= n <= 9
代码结果
运行时间: 120 ms, 内存: 15.3 MB
/*
* This Java Stream solution also uses backtracking to solve the n-Queens problem,
* but it leverages Java Streams for more declarative style.
*/
import java.util.stream.IntStream;
public class NQueensStream {
private int count = 0;
public int totalNQueens(int n) {
backtrack(0, n, new boolean[n], new boolean[2 * n], new boolean[2 * n]);
return count;
}
private void backtrack(int row, int n, boolean[] cols, boolean[] d1, boolean[] d2) {
if (row == n) { // All queens are placed
count++;
return;
}
IntStream.range(0, n).forEach(col -> {
int id1 = col - row + n;
int id2 = col + row;
if (!cols[col] && !d1[id1] && !d2[id2]) {
cols[col] = true; d1[id1] = true; d2[id2] = true;
backtrack(row + 1, n, cols, d1, d2);
cols[col] = false; d1[id1] = false; d2[id2] = false; // Reset state
}
});
}
}
解释
方法:
这道题使用回溯算法求解。从第一行开始，尝试在每一列放置皇后，并检查是否与已经放置的皇后冲突。如果当前放置的皇后不与之前的皇后冲突，则继续放置下一行的皇后；否则，回溯到上一行，尝试将皇后放置在其他列。当所有的皇后都成功放置时，将当前的棋盘状态加入答案数组。最后返回答案数组的长度即为不同的解决方案的数量。
时间复杂度:
O(n^(n+1))
空间复杂度:
O(n)
代码细节讲解
🦆
在回溯法中，你是如何确定哪些列和对角线已经被攻击，从而避免在这些位置放置皇后的？
▷🦆
当你提到检查皇后冲突时，为什么没有考虑下方和左下、右下对角线的冲突？
▷🦆
递归函数`backtrack`中递归退出条件是`i == n`，这里的i具体代表什么意义？
▷相关问题
N 皇后
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例 1：
输入：n = 4 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] 解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：
输入：n = 1 输出：[["Q"]]
提示：
1 <= n <= 9