AcWing0843 n-皇后问题
n−皇后问题是指将 n 个皇后放在 n×n 的国际象棋棋盘上,使得皇后不能相互攻击到,即任意两个皇后都不能处于同一行、同一列或同一斜线上。
现在给定整数 n,请你输出所有的满足条件的棋子摆法。
输入格式
共一行,包含整数 n 。
输出格式
每个解决方案占 n 行,每行输出一个长度为 n 的字符串,用来表示完整的棋盘状态。
其中 .
表示某一个位置的方格状态为空,Q
表示某一个位置的方格上摆着皇后。
每个方案输出完成后,输出一个空行。
注意:行末不能有多余空格。
输出方案的顺序任意,只要不重复且没有遗漏即可。
数据范围
1 ≤ n ≤ 9
输入样例:
4
输出样例:
.Q..
...Q
Q...
..Q.
..Q.
Q...
...Q
.Q..
算法思想:
按行进行DFS型枚举。对与每一行,按列找到第一个列、主对角线、副对角线均未被占据的棋盘位置,占据该位置并继续向下搜索,最后回溯状态。当搜索到最后一行结束时,打印棋盘状态。
使用到的辅助信息如下:
-
int pos[1..n]
维护棋盘状态。pos[i] == j
表示第i
行的第j
列放置皇后。 -
bool col[1..n]
维护列状态。col[j] == true
表示第j
列已被占据。 -
bool dg[1..(2n-1)]
维护主对角线状态。dg[u] == true
表示主对角线 $y=x+u-n$ 已被占据。其中u == j - i + n
,表示第i
行第j
列所在的主对角线。 -
bool cdg[2..2n]
维护副对角线状态。cdg[v] == true
表示副对角线 $y=-x+v$ 已被占据。其中v == i + j
,表示第i
行第j
列所在的副对角线。 -
int i = 1
维护当前枚举的行号。
注意,我们以棋盘的左上角为原点,向下为 x 轴(行 i
方向),向右为 y 轴(列 j
方向),建立平面直角坐标系。
算法 1 -排列型枚举(25 ms):
#include <iostream>
#include <string>
using namespace std;
const int N = 10;
int pos[N], n;
bool col[N], dg[2 * N], cdg[2 * N];
// 根据 pos[1..n] 打印棋盘
void print() {
for (int i = 1; i <= n; ++i) {
string s(n, '.');
s[pos[i] - 1] = 'Q';
cout << s << endl;
}
cout << endl;
}
// 从第 i 行开始向下枚举
void DFS(int i) {
// 若所有行状态全部已枚举,则打印棋盘
if (i > n) {
print();
return;
}
for (int j = 1; j <= n; ++j) {
// 找到当前行的第一个列与主副对角线均未被占据的位置
if (col[j] || dg[j - i + n] || cdg[i + j]) {
continue;
}
// 占据该位置并向下搜索
col[j] = dg[j - i + n] = cdg[i + j] = true;
pos[i] = j;
DFS(i + 1);
// 状态回溯
col[j] = dg[j - i + n] = cdg[i + j] = false;
}
}
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
cin >> n;
DFS(1);
return 0;
}