AcWing 843：n-皇后问题 ← dfs

【题目来源】
https://www.acwing.com/problem/content/845/
https://www.lanqiao.cn/problems/1508/learning/
https://www.luogu.com.cn/problem/P1219

【题目描述】
n 皇后问题是指将 n 个皇后放在 n×n 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。

现在给定整数 n，请你输出所有的满足条件的棋子摆法。

【输入格式】
共一行，包含整数 n。

【输出格式】
每个解决方案占 n 行，每行输出一个长度为 n 的字符串，用来表示完整的棋盘状态。
其中 . 表示某一个位置的方格状态为空，Q 表示某一个位置的方格上摆着皇后。
每个方案输出完成后，输出一个空行。
注意：行末不能有多余空格。
输出方案的顺序任意，只要不重复且没有遗漏即可。

【数据范围】
1≤n≤9

【输入样例】
4

【输出样例】
.Q..
...Q
Q...
..Q.

..Q.
Q...
...Q
.Q..

【算法分析】
● 请注意，n 维方阵中 row-col 的范围是 [-n+1,n-1]，row+col 的范围是 [0,2n-2]，所以主对角线和次对角线的数量都为 2n-1，即存储主对角线及次对角线数量的数组长度都为 2n-1。

● ​​​​​​​主对角线是棋盘中从左上到右下的斜线，主斜线 zxx[] 是棋盘中与主对角线平行的斜线。
观察易知，同一主斜线上各棋格的横坐标 x 减去纵坐标 y 的差相等。即说明同一主斜线上多个棋格可通过减法映射到数组中的同一位置。此时，若判断某条主斜线上是否出现过一次皇后，即查看 zxx[x - y] 是否为空即可。但这样做减法时可能会得到一个负数，是没法直接映射到数组中的，因此在主斜线上做判断时统一加上一个常量保证非负，即 zxx[x - y + n]。

● 副对角线是棋盘中从左下到右上的斜线，副斜线 fxx[] 是棋盘中与副对角线平行的斜线。
观察易知，同一副斜线上各棋格的横坐标 x 加上纵坐标 y 的和相等。即说明同一副斜线上多个棋格可通过加法映射到数组中的同一位置。此时，若判断某条副斜线上是否出现过一次皇后，即查看 fxx[x + y] 是否为空即可。

● 如下代码是 N 皇后问题回溯算法的核心部分。

for(int i=0; i<n; i++) {if(!col[i] && !fxx[i+k] && !zxx[n-i+k]) {a[k][i]='Q';col[i]=fxx[i+k]=zxx[n-i+k]=1;dfs(k+1);col[i]=fxx[i+k]=zxx[n-i+k]=0;a[k][i]='.';}
}

逐行解释如下：
（1）for(int i=0; i<n; i++)：尝试在当前行 k 的每一列 i 放置皇后
（2）if(!col[i] && !fxx[i+k] && !zxx[n-i+k])：检查三个条件
!col[i] 表示第 i 列没有皇后
!fxx[i+k] 表示副斜线（左下到右上）没有皇后
!zxx[n-i+k] 表示主斜线（左上到右下）没有皇后
（3）如果条件满足：
a[k][i]='Q'：在棋盘 k 行 i 列放置皇后
col[i]=fxx[i+k]=zxx[n-i+k]=1：标记列和两个对角线已被占用
dfs(k+1)：递归处理下一行
（4）回溯部分：
col[i]=fxx[i+k]=zxx[n-i+k]=0：撤销标记
a[k][i]='.'：移除皇后

如上核心代码实现了通过三个一维数组 (col,zxx,fxx) 替代二维数组检查，将空间复杂度从 O(N²) 降到O(N)，是 N 皇后问题的优化解法。

【算法代码】

#include <bits/stdc++.h>
using namespace std;const int N=10;
char a[N][N];
bool zxx[N<<1],fxx[N<<1],col[N];
int n;void dfs(int k) { //k:rowif(k==n) {for(int i=0; i<n; i++) {for(int j=0; j<n; j++) {cout<<a[i][j];}cout<<endl;}cout<<endl;return;}for(int i=0; i<n; i++) { //i:columnif(!col[i] && !fxx[i+k] && !zxx[n-i+k]) {a[k][i]='Q';col[i]=fxx[i+k]=zxx[n-i+k]=1;dfs(k+1);col[i]=fxx[i+k]=zxx[n-i+k]=0;a[k][i]='.';}}
}int main() {cin>>n;for(int i=0; i<n; i++)for(int j=0; j<n; j++)a[i][j]='.';dfs(0);return 0;
}/*
in:
4out:
.Q..
...Q
Q...
..Q...Q.
Q...
...Q
.Q..
*/

【参考文献】
https://m.w3cschool.cn/hellocpp/hellocpp-vq793tl7.html
https://www.acwing.com/solution/content/30231/
https://www.lanqiao.cn/problems/1508/learning/
https://www.luogu.com.cn/problem/P1219
https://www.acwing.com/solution/content/179688/