题目大意
将$n$个皇后放在$n*n$的棋盘上,要求任意两皇后不处于同一行,同一列,同一主或副对角线。输入$n$,输出所有合法放置方案。
解题思路
每一行只能放一个皇后,也就是说可设计dfs每层考虑一行,相比于考虑每一个格子大大省时。当然每层考虑一列/一条对角线也可以,只是根据CSAPP的知识,显然考虑行增加了缓存命中。本题还有一个小技巧是如何快速判断当前对角线是否已经有皇后。设一个皇后放在了$(u,j)$上,那么这个皇后所在的主对角线可用函数式$j=u+b$表示,每条主对角线都对应唯一的截距$b$,所以通过$b=j-u$便可快速找到当前主对角线。另外要注意的是,$j-u$可能小于零,而$C++$不支持数组负数下标,因此需加上偏移量$n$,于是$dg[j-u+n]$存储了一条主对角线上是否有皇后。同理,副对角线可推出$udg[u+j]$,区别是$u+j$一定是正数无需加上偏移量。
具体代码
#include<iostream>
using namespace std;
const int N=20;
char g[N][N];
bool col[N],dg[N],udg[N];
int n;
void dfs(int u) //当前正考虑第u行
{
if(u==n+1) //已经考虑完了整个棋盘
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cout<<g[i][j];
}
puts("");
}
puts("");
return;
}
for(int j=1;j<=n;j++) //放在这一行的第j个位置
{
if(!col[j]&&!dg[j-u+n]&&!udg[j+u]) //确保不和已放的皇后冲突
{
g[u][j]='Q',col[j]=true,dg[j-u+n]=true,udg[j+u]=true;
dfs(u+1);
g[u][j]='.',col[j]=false,dg[j-u+n]=false,udg[j+u]=false; //回溯恢复现场
}
}
}
int main()
{
cin>>n;
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
g[i][j]='.';
dfs(1);
return 0;
}