51. 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原站题解
java 解法, 执行用时: 1 ms, 内存消耗: 41.8 MB, 提交时间: 2023-03-21 10:00:34
class Solution {
private int n;
private int[] col;
private boolean[] onPath, diag1, diag2;
private final List<List<String>> ans = new ArrayList<>();
public List<List<String>> solveNQueens(int n) {
this.n = n;
col = new int[n];
onPath = new boolean[n];
diag1 = new boolean[n * 2 - 1];
diag2 = new boolean[n * 2 - 1];
dfs(0);
return ans;
}
private void dfs(int r) {
if (r == n) {
List<String> board = new ArrayList<>(n);
for (int c : col) {
char[] row = new char[n];
Arrays.fill(row, '.');
row[c] = 'Q';
board.add(new String(row));
}
ans.add(board);
return;
}
for (int c = 0; c < n; ++c) {
int rc = r - c + n - 1;
if (!onPath[c] && !diag1[r + c] && !diag2[rc]) {
col[r] = c;
onPath[c] = diag1[r + c] = diag2[rc] = true;
dfs(r + 1);
onPath[c] = diag1[r + c] = diag2[rc] = false; // 恢复现场
}
}
}
}
golang 解法, 执行用时: 8 ms, 内存消耗: 3.1 MB, 提交时间: 2023-03-21 10:00:19
func solveNQueens(n int) (ans [][]string) {
col := make([]int, n)
onPath := make([]bool, n)
diag1 := make([]bool, n*2-1)
diag2 := make([]bool, n*2-1)
var dfs func(int)
dfs = func(r int) {
if r == n {
board := make([]string, n)
for i, c := range col {
board[i] = strings.Repeat(".", c) + "Q" + strings.Repeat(".", n-1-c)
}
ans = append(ans, board)
return
}
for c, on := range onPath {
rc := r - c + n - 1
if !on && !diag1[r+c] && !diag2[rc] {
col[r] = c
onPath[c], diag1[r+c], diag2[rc] = true, true, true
dfs(r + 1)
onPath[c], diag1[r+c], diag2[rc] = false, false, false // 恢复现场
}
}
}
dfs(0)
return
}
python3 解法, 执行用时: 60 ms, 内存消耗: 15.2 MB, 提交时间: 2023-03-21 10:00:07
# 回溯法
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
m = n * 2 - 1
ans = []
col = [0] * n
on_path, diag1, diag2 = [False] * n, [False] * m, [False] * m
def dfs(r: int) -> None:
if r == n:
ans.append(['.' * c + 'Q' + '.' * (n - 1 - c) for c in col])
return
for c, on in enumerate(on_path):
if not on and not diag1[r + c] and not diag2[r - c]:
col[r] = c
on_path[c] = diag1[r + c] = diag2[r - c] = True
dfs(r + 1)
on_path[c] = diag1[r + c] = diag2[r - c] = False # 恢复现场
dfs(0)
return ans