51. N 皇后
题目描述
皇后能攻击同一行、同一列以及两条对角线上的任意棋子。输入整数 n，要在 n x n 的棋盘上摆 n 个皇后，使任意两个皇后都互不攻击。
找出所有满足要求的摆法并返回。每种摆法用一个字符串数组表示，数组第 i 项对应棋盘第 i 行，字符 'Q' 表示皇后，'.' 表示空格。
各种摆法在结果中的先后顺序不限。
示例 1
输入：n = 4 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：4 x 4 棋盘上一共只有 2 种合法摆法。
示例 2
输入：n = 1 输出：[["Q"]]
解释：1 x 1 棋盘只能放一个皇后。
数据范围
1 <= n <= 9
解题思路：回溯 + 集合剪枝
按行放置并用集合剪枝。
为什么正确
三个集合排除列与两条对角线冲突。
复杂度分析
时间 O(n!)，额外空间 O(n)。
易错点
注意边界条件并在回溯或弹出后恢复状态。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def solveNQueens(self,n):
out=[];b=[['.']*n for _ in range(n)];C=set();D=set();E=set()
def f(r):
if r==n:out.append([''.join(x) for x in b]);return
for c in range(n):
if c in C or r-c in D or r+c in E:continue
C.add(c);D.add(r-c);E.add(r+c);b[r][c]='Q';f(r+1);b[r][c]='.';C.remove(c);D.remove(r-c);E.remove(r+c)
f(0);return outclass Solution {
List<List<String>> out; char[][] b; Set<Integer> C, D, E; int n;
public List<List<String>> solveNQueens(int n) {
this.n = n; out = new ArrayList<>(); b = new char[n][n]; for (char[] x : b) Arrays.fill(x, '.'); C = new HashSet<>(); D = new HashSet<>(); E = new HashSet<>();
f(0); return out;
}
void f(int r) {
if (r == n) { List<String> s = new ArrayList<>(); for (char[] x : b) s.add(new String(x)); out.add(s); return; }
for (int c = 0; c < n; c++) {
if (C.contains(c) || D.contains(r - c) || E.contains(r + c)) continue;
C.add(c); D.add(r - c); E.add(r + c); b[r][c] = 'Q'; f(r + 1); b[r][c] = '.'; C.remove(c); D.remove(r - c); E.remove(r + c);
}
}
}class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> out; vector<string> b(n, string(n, '.')); unordered_set<int> C, D, E;
function<void(int)> f = [&](int r) {
if (r == n) { out.push_back(b); return; }
for (int c = 0; c < n; c++) {
if (C.count(c) || D.count(r - c) || E.count(r + c)) continue;
C.insert(c); D.insert(r - c); E.insert(r + c); b[r][c] = 'Q'; f(r + 1); b[r][c] = '.'; C.erase(c); D.erase(r - c); E.erase(r + c);
}
};
f(0); return out;
}
};func solveNQueens(n int) [][]string {
out, b := [][]string{}, make([][]byte, n)
for i := range b {
b[i] = []byte(strings.Repeat(".", n))
}
C, D, E := map[int]bool{}, map[int]bool{}, map[int]bool{}
var f func(r int)
f = func(r int) {
if r == n {
s := []string{}
for _, x := range b { s = append(s, string(x)) }
out = append(out, s)
return
}
for c := 0; c < n; c++ {
if C[c] || D[r-c] || E[r+c] { continue }
C[c], D[r-c], E[r+c] = true, true, true; b[r][c] = 'Q'; f(r + 1); b[r][c] = '.'
delete(C, c); delete(D, r-c); delete(E, r+c)
}
}
f(0)
return out
}var solveNQueens = function(n) {
const out = [], b = Array.from({ length: n }, () => Array(n).fill('.')), C = new Set(), D = new Set(), E = new Set();
const f = r => {
if (r === n) { out.push(b.map(x => x.join(''))); return; }
for (let c = 0; c < n; c++) {
if (C.has(c) || D.has(r - c) || E.has(r + c)) continue;
C.add(c); D.add(r - c); E.add(r + c); b[r][c] = 'Q'; f(r + 1); b[r][c] = '.'; C.delete(c); D.delete(r - c); E.delete(r + c);
}
};
f(0); return out;
};function solveNQueens(n: number): string[][] {
const out: string[][] = [], b: string[][] = Array.from({ length: n }, () => Array(n).fill('.')), C = new Set<number>(), D = new Set<number>(), E = new Set<number>();
const f = (r: number): void => {
if (r === n) { out.push(b.map(x => x.join(''))); return; }
for (let c = 0; c < n; c++) {
if (C.has(c) || D.has(r - c) || E.has(r + c)) continue;
C.add(c); D.add(r - c); E.add(r + c); b[r][c] = 'Q'; f(r + 1); b[r][c] = '.'; C.delete(c); D.delete(r - c); E.delete(r + c);
}
};
f(0); return out;
};其他解法
两种方法都是逐行回溯；集合版本直观，位运算版本把冲突判断和候选枚举压缩成几条整数运算，速度更快。
解法 2：回溯 + 位运算 时间 O(n!)，空间 O(n)
用三个整数 cols、d1、d2 的二进制位记录被列和两条对角线占用的位置。每行可放的位置是 full & ~(cols | d1 | d2)。用 avail & -avail 依次取出最低位的 1 放皇后。进入下一行时，d1 左移一位，d2 右移一位，表示对角线向下延伸。
复杂度和集合版本相同，但位运算代替哈希查找，常数小很多。可用位置直接枚举，不用逐列试探。代码需要理解移位和取最低位的技巧。
class Solution:
def solveNQueens(self, n):
out = []
queens = [0] * n
full = (1 << n) - 1
def dfs(r, cols, d1, d2):
if r == n:
out.append(['.' * c + 'Q' + '.' * (n - c - 1) for c in queens])
return
avail = full & ~(cols | d1 | d2)
while avail:
bit = avail & -avail
avail &= avail - 1
queens[r] = bit.bit_length() - 1
dfs(r + 1, cols | bit, ((d1 | bit) << 1) & full, (d2 | bit) >> 1)
dfs(0, 0, 0, 0)
return outclass Solution {
List<List<String>> out = new ArrayList<>();
int[] queens;
int n, full;
public List<List<String>> solveNQueens(int n) {
this.n = n;
queens = new int[n];
full = (1 << n) - 1;
dfs(0, 0, 0, 0);
return out;
}
void dfs(int r, int cols, int d1, int d2) {
if (r == n) {
List<String> b = new ArrayList<>();
for (int c : queens) {
char[] row = new char[n];
Arrays.fill(row, '.');
row[c] = 'Q';
b.add(new String(row));
}
out.add(b);
return;
}
int avail = full & ~(cols | d1 | d2);
while (avail != 0) {
int bit = avail & -avail;
avail &= avail - 1;
queens[r] = Integer.numberOfTrailingZeros(bit);
dfs(r + 1, cols | bit, ((d1 | bit) << 1) & full, (d2 | bit) >> 1);
}
}
}class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> out;
vector<int> queens(n);
int full = (1 << n) - 1;
function<void(int, int, int, int)> dfs = [&](int r, int cols, int d1, int d2) {
if (r == n) {
vector<string> b;
for (int c : queens) {
string row(n, '.');
row[c] = 'Q';
b.push_back(row);
}
out.push_back(b);
return;
}
int avail = full & ~(cols | d1 | d2);
while (avail) {
int bit = avail & -avail;
avail &= avail - 1;
queens[r] = __builtin_ctz(bit);
dfs(r + 1, cols | bit, ((d1 | bit) << 1) & full, (d2 | bit) >> 1);
}
};
dfs(0, 0, 0, 0);
return out;
}
};func solveNQueens(n int) [][]string {
out := [][]string{}
queens := make([]int, n)
full := (1 << n) - 1
var dfs func(r, cols, d1, d2 int)
dfs = func(r, cols, d1, d2 int) {
if r == n {
b := []string{}
for _, c := range queens {
row := []byte(strings.Repeat(".", n))
row[c] = 'Q'
b = append(b, string(row))
}
out = append(out, b)
return
}
avail := full &^ (cols | d1 | d2)
for avail != 0 {
bit := avail & -avail
avail &= avail - 1
queens[r] = bits.TrailingZeros(uint(bit))
dfs(r+1, cols|bit, ((d1|bit)<<1)&full, (d2|bit)>>1)
}
}
dfs(0, 0, 0, 0)
return out
}var solveNQueens = function(n) {
const out = [], queens = Array(n).fill(0), full = (1 << n) - 1;
const dfs = (r, cols, d1, d2) => {
if (r === n) {
out.push(queens.map(c => '.'.repeat(c) + 'Q' + '.'.repeat(n - c - 1)));
return;
}
let avail = full & ~(cols | d1 | d2);
while (avail) {
const bit = avail & -avail;
avail &= avail - 1;
queens[r] = 31 - Math.clz32(bit);
dfs(r + 1, cols | bit, ((d1 | bit) << 1) & full, (d2 | bit) >> 1);
}
};
dfs(0, 0, 0, 0);
return out;
};function solveNQueens(n: number): string[][] {
const out: string[][] = [], queens: number[] = Array(n).fill(0), full = (1 << n) - 1;
const dfs = (r: number, cols: number, d1: number, d2: number): void => {
if (r === n) {
out.push(queens.map(c => '.'.repeat(c) + 'Q' + '.'.repeat(n - c - 1)));
return;
}
let avail = full & ~(cols | d1 | d2);
while (avail) {
const bit = avail & -avail;
avail &= avail - 1;
queens[r] = 31 - Math.clz32(bit);
dfs(r + 1, cols | bit, ((d1 | bit) << 1) & full, (d2 | bit) >> 1);
}
};
dfs(0, 0, 0, 0);
return out;
}