LeetCode 面试题 08.12. 八皇后
目录
题目描述
题意分析
在
n × n的棋盘上摆n个皇后，要求任意两个皇后互不攻击——即不在同一行、同一列，也不在同一条斜线上。需要返回所有合法摆法，每种摆法用n个字符串表示，Q是皇后，.是空位。第一个关键推论来自「棋盘是
n × n、皇后恰好n个、且同行不能有两个」：每一行必然、且只能放一个皇后。这把问题从「在 $n^2$ 个格子里选 $n$ 个」压缩成「为每一行各选一个列号」，搜索空间从组合数直接降到排列级别。第二个推论是同列也只能有一个，所以
n行的列号构成 0 到n - 1的一个排列，剩下要排除的就只有斜线冲突。约束信号是
n很小（不超过 9），说明题目本来就接受指数级的穷举搜索，重点不在剪枝有多狠，而在冲突判断是否写对、状态是否恢复干净。边界包括
n = 1（唯一解是单个Q）、n = 2和n = 3（无解，必须返回空列表而不是报错），以及记录答案时棋盘必须做快照。
解法：按行回溯 + 三组占用标记
核心思路
棋盘有
n行且要放n个皇后，同一行又不能放两个，因此每行恰好选择一列。按行递归后，第row层只需枚举这一行的列，搜索空间由任意选格子缩小为排列型搜索。新皇后只可能与前面行的皇后发生列或对角线冲突。三个编号可以在 $O(1)$ 时间判断：
- 列：
col。- 主对角线：
row - col + n - 1。- 副对角线：
row + col。两类对角线编号范围都是
0到2n - 2。进入dfs(row)时维持不变量：前row行各有一个互不攻击的皇后，三个占用数组与棋盘状态完全一致。选择位置后同时标记，递归返回后原样撤销，所以下一个分支看到的状态与进入本层时相同。当
row == n时，所有行都已合法放置，当前棋盘就是一个解。逐行转成字符串相当于做快照，避免后续回溯修改已记录答案。算法枚举每个合法前缀，因此不会漏解；每行按不同列展开，也不会重复生成同一棋盘。
解题步骤
- 初始化全为
.的棋盘，以及列、主对角线、副对角线三个占用数组。- 在第
row行依次尝试每个col，计算两个对角线编号。- 任一编号已占用就剪枝；否则放置
Q并设置三组标记。- 递归处理下一行，返回后撤销棋盘和全部标记。
row == n时复制棋盘到答案。以
n = 4为例，首行选第 2 列后，可依次选择第 4、1、3 列，得到[".Q..","...Q","Q...","..Q."]。若某行没有可选列，本分支直接回退到上一行换列。
代码实现
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution {
public List<List<String>> solveNQueens(int n) {
char[][] board = new char[n][n];
for (char[] row : board) {
Arrays.fill(row, '.');
}
List<List<String>> answer = new ArrayList<>();
dfs(0, board, new boolean[n], new boolean[2 * n - 1],
new boolean[2 * n - 1], answer);
return answer;
}
private void dfs(int row, char[][] board, boolean[] columns,
boolean[] diagonals, boolean[] antiDiagonals,
List<List<String>> answer) {
int n = board.length;
if (row == n) {
List<String> solution = new ArrayList<>(n);
for (char[] line : board) {
solution.add(new String(line));
}
answer.add(solution);
return;
}
for (int col = 0; col < n; col++) {
int diagonal = row - col + n - 1;
int antiDiagonal = row + col;
if (columns[col] || diagonals[diagonal] || antiDiagonals[antiDiagonal]) {
continue;
}
board[row][col] = 'Q';
columns[col] = true;
diagonals[diagonal] = true;
antiDiagonals[antiDiagonal] = true;
dfs(row + 1, board, columns, diagonals, antiDiagonals, answer);
board[row][col] = '.';
columns[col] = false;
diagonals[diagonal] = false;
antiDiagonals[antiDiagonal] = false;
}
}
}
func solveNQueens(n int) [][]string {
board := make([][]byte, n)
for row := range board {
board[row] = make([]byte, n)
for col := range board[row] {
board[row][col] = '.'
}
}
answer := make([][]string, 0)
columns := make([]bool, n)
diagonals := make([]bool, 2*n-1)
antiDiagonals := make([]bool, 2*n-1)
var dfs func(int)
dfs = func(row int) {
if row == n {
solution := make([]string, n)
for i := range board {
solution[i] = string(board[i])
}
answer = append(answer, solution)
return
}
for col := 0; col < n; col++ {
diagonal := row - col + n - 1
antiDiagonal := row + col
if columns[col] || diagonals[diagonal] || antiDiagonals[antiDiagonal] {
continue
}
board[row][col] = 'Q'
columns[col] = true
diagonals[diagonal] = true
antiDiagonals[antiDiagonal] = true
dfs(row + 1)
board[row][col] = '.'
columns[col] = false
diagonals[diagonal] = false
antiDiagonals[antiDiagonal] = false
}
}
dfs(0)
return answer
}
复杂度分析
- 时间复杂度：上界为 $O(n \cdot n! + S \cdot n^2)$，其中 $S$ 是解的数量。前一项来自排列型搜索及每层枚举列，后一项是复制每个解的输出成本。
- 空间复杂度：$O(n^2)$，棋盘占主要空间，标记数组和递归深度为 $O(n)$；返回结果不计入额外空间。
关键点总结
- “每行恰放一个”决定了按行回溯，而不是在 $n^2$ 个格子中任意选点。
row - col与row + col分别唯一标识两类对角线。- 主对角线编号可能为负，必须平移
n - 1。- 放置和撤销必须严格对称，记录答案必须复制当前棋盘。
- 面试追问优化时可提位掩码压缩三组标记，但数组版本更直观，且已满足本题规模。
易错点总结
- 对角线数组只开长度
n，在row + col >= n时会越界。- 主对角线忘记加
n - 1，右上区域会产生负下标。- 递归返回后漏撤销任一标记，会错误剪掉其他分支。
row == n - 1时就记录，会漏放最后一行。- 保存棋盘行的可变引用而非字符串快照，所有答案会被后续回溯覆盖。
- 只检查列、不检查两类对角线，会收集互相攻击的非法方案。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 51. N 皇后 | 困难 | 同题的标准棋盘输出 |
| 52. N 皇后 II | 困难 | 只计数可用位运算压状态 |
| 37. 解数独 | 困难 | 行列宫三重约束回溯 |
| 46. 全排列 | 中等 | 排列型回溯与使用标记 |
| 79. 单词搜索 | 中等 | 网格上的路径回溯 |
| 22. 括号生成 | 中等 | 剪枝条件的构造 |
| 39. 组合总和 | 中等 | 组合型回溯去重 |