【题目来源】
AcWing：843. n-皇后问题 - AcWing题库
【题目描述】
\(n\)-皇后问题是指将 \(n\) 个皇后放在 \(n\times n\) 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。
现在给定整数 \(n\)，请你输出所有的满足条件的棋子摆法。
【输入】
共一行，包含整数 \(n\)。
【输出】
每个解决方案占 \(n\) 行，每行输出一个长度为 \(n\) 的字符串，用来表示完整的棋盘状态。
其中 . 表示某一个位置的方格状态为空，Q 表示某一个位置的方格上摆着皇后。
每个方案输出完成后，输出一个空行。
注意：行末不能有多余空格。
输出方案的顺序任意，只要不重复且没有遗漏即可。
【输入样例】
4
【输出样例】
.Q..
...Q
Q...
..Q...Q.
Q...
...Q
.Q..
【解题思路】
【算法标签】
《AcWing 843 n-皇后问题》 #DFS# #剪枝#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 20; // 定义棋盘最大尺寸int n; // 棋盘大小（n×n）
char g[N][N]; // 棋盘布局
bool col[N]; // 标记列是否被占用
bool dg[N]; // 标记正对角线是否被占用（左上到右下）
bool udg[N]; // 标记反对角线是否被占用（右上到左下）// 深度优先搜索放置皇后
void dfs(int u) // u: 当前处理的行号
{// 终止条件：所有行都已放置皇后if (u == n) {// 打印当前棋盘布局for (int i = 0; i < n; i++) puts(g[i]);puts(""); // 空行分隔不同解return;}// 尝试在当前行的每一列放置皇后for (int i = 0; i < n; i++) {// 检查当前位置是否安全（列、对角线无冲突）if (!col[i] && !dg[u + i] && !udg[n - u + i]) {g[u][i] = 'Q'; // 放置皇后col[i] = dg[u + i] = udg[n - u + i] = true; // 标记占用dfs(u + 1); // 递归处理下一行// 回溯：恢复状态col[i] = dg[u + i] = udg[n - u + i] = false;g[u][i] = '.';}}
}int main()
{cin >> n; // 输入棋盘大小// 初始化棋盘（全部置为'.'）for (int i = 0; i < n; i++)for (int j = 0; j < n; j++) g[i][j] = '.';dfs(0); // 从第0行开始放置皇后return 0;
}
// 更为原始的算法
#include <bits/stdc++.h>
using namespace std;const int N = 20; // 定义棋盘最大尺寸int n; // 棋盘大小（n×n）
char g[N][N]; // 棋盘布局
bool row[N]; // 标记行是否被占用
bool col[N]; // 标记列是否被占用
bool dg[N]; // 标记正对角线是否被占用（左上到右下）
bool udg[N]; // 标记反对角线是否被占用（右上到左下）// 深度优先搜索放置皇后
void dfs(int x, int y, int s) // x: 当前行, y: 当前列, s: 已放置皇后数
{// 列越界处理：换行if (y == n) {y = 0;x++;}// 终止条件：处理完所有格子if (x == n) {// 如果放置了n个皇后，输出解if (s == n) {for (int i = 0; i < n; i++) puts(g[i]);puts(""); // 空行分隔不同解}return;}// 情况1：当前位置不放皇后dfs(x, y + 1, s);// 情况2：当前位置放皇后（需满足条件）if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n]) {g[x][y] = 'Q'; // 放置皇后row[x] = col[y] = dg[x + y] = udg[x - y + n] = true; // 标记占用dfs(x, y + 1, s + 1); // 递归处理下一个位置// 回溯：恢复状态row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;g[x][y] = '.';}
}int main()
{cin >> n; // 输入棋盘大小// 初始化棋盘（全部置为'.'）for (int i = 0; i < n; i++)for (int j = 0; j < n; j++) g[i][j] = '.';dfs(0, 0, 0); // 从(0,0)位置开始搜索return 0;
}
【运行结果】
4
.Q..
...Q
Q...
..Q...Q.
Q...
...Q
.Q..