如何用回溯法解决N皇后问题？
摘要：👑 N 皇后问题学习笔记（含完整 C++ 代码） 📌 题目简介 N 皇后问题是指将 N 个皇后放置在 N×N 的国
👑 N 皇后问题学习笔记（含完整 C++ 代码）
📌 题目简介
N 皇后问题是指将 N 个皇后放置在 N×N 的国际象棋棋盘上，使得它们不能相互攻击，即任意两个皇后都不能处于同一行、同一列或同一对角线上。返回所有符合要求的摆法。
🔍 解题思路：回溯法（Backtracking）
回溯框架：
从第 0 行开始尝试放置皇后；
在每一行中，遍历所有列，尝试放皇后；
如果当前位置不受攻击，就放下皇后并继续处理下一行；
如果下一行无合法选择，则撤回当前选择（回溯）；
最终当所有行都放完皇后，即找到一个合法解。
🧠 冲突判断规则
放置皇后之前，需确保当前位置不与已放置的皇后在：
同一列；
同一主对角线（左上到右下）；
同一副对角线（右上到左下）上。
可以用以下方式判断冲突：
列冲突：使用一个 vector<bool> cols；
主对角线冲突：diag1[row - col + n - 1]；
副对角线冲突：diag2[row + col]。
🧱 完整 C++ 源码
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
unordered_set<int> diag1; // row + col（主对角线）
unordered_set<int> diag2; // row - col（副对角线）
unordered_set<int> usedCols; // 已占用的列
vector<vector<int>> solutions; // 记录所有解，每个解为一组Q所在列号
void DFS(int row, int n, vector<int> ¤tPath)
{
if (row == n)
{
solutions.push_back(currentPath);
return;
}
for (int colIndex = 0; colIndex < n; colIndex++)
{
if (usedCols.count(colIndex) || diag1.count(row + colIndex) || diag2.count(row - colIndex))
{
continue;
}
// 标记当前位置
usedCols.insert(colIndex);
diag1.insert(row + colIndex);
diag2.insert(row - colIndex);
currentPath.push_back(colIndex);
DFS(row + 1, n, currentPath);
// 回溯
usedCols.erase(colIndex);
diag1.erase(row + colIndex);
diag2.erase(row - colIndex);
currentPath.pop_back();
}
}
int main()
{
int n;
cin >> n;
vector<int> currentPath;
DFS(0, n, currentPath);
for (const auto &solution : solutions)
{
for (int colIndex : solution)
{
for (int i = 0; i < n; i++)
{
cout << (i == colIndex ? "Q" : ".");
}
cout << '\n';
}
cout << '\n';
}
return 0;
}
🧪 示例输出
输入：
4
输出：
. Q . .
. . . Q
Q . . .
. . Q .
. . Q .
Q . . .
. . . Q
. Q . .
📌 关键点总结
关键点
描述
回溯法
每一层尝试在某一行放一个皇后
剪枝优化
用三个布尔数组快速判断是否冲突
时间复杂度
O(N!)，因为每一行都尝试 N 个位置
空间复杂度
O(N²) 存储棋盘和标记数组