51. N 皇后
4 min
题目
解法：回溯法
思路
核心思想是回溯法（DFS）逐行尝试放置皇后，通过剪枝排除无效位置。
正确性基于递归不变量——已放置的皇后始终满足约束条件。每行选择一个列放置皇后，若该位置与之前皇后无列和对角线冲突，则继续递归下一行；否则回溯尝试其他列。由于每行只放一个皇后，且检查所有冲突，因此所有合法解都会被枚举，无效路径会被及时剪枝。
- Step 1: 初始化 n×n 棋盘，从第 0 行开始深度优先搜索。
- Step 2: 在当前行遍历每一列，检查该位置是否与已放置皇后冲突。
- Step 3: 若无冲突，放置皇后并递归处理下一行。
- Step 4: 当成功放置 n 个皇后时，将当前棋盘加入结果集。
- Step 5: 回溯，撤销当前行的皇后，尝试其他列。
复杂度
- 时间复杂度: ，最坏情况需尝试所有排列，剪枝大幅减少实际搜索量。
- 空间复杂度: ，递归栈深度 和棋盘存储 。
代码
class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> ans;
vector<string> board(n, string(n, '.'));
dfs(board, 0, ans);
return ans;
}
void dfs(vector<string>& board, int row, vector<vector<string>>& ans) {
int n = board.size();
if (row == n) {
ans.push_back(board);
return;
}
for (int col = 0; col < n; col++) {
if (isValid(board, row, col)) {
board[row][col] = 'Q';
dfs(board, row + 1, ans);
board[row][col] = '.'; // 回溯
}
}
}
class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> ans;
vector<string> board(n, string(n, '.'));
dfs(board, 0, ans);
return ans;
}
void dfs(vector<string>& board, int row, vector<vector<string>>& ans) {
int n = board.size();
if (row == n) {
ans.push_back(board);
return;
}
for (int col = 0; col < n; col++) {
if (isValid(board, row, col)) {
board[row][col] = 'Q';
dfs(board, row + 1, ans);
board[row][col] = '.'; // 回溯
}
}
}
bool isValid(const vector<string>& board, int row, int col) {
int n = board.size();
// 检查同一列
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;
}
};