ACWING板子题地址：https://www.acwing.com/problem/content/description/845/
题中已经说的很清楚了，什么叫n皇后。对于一个棋子的摆放，我们应该保证这个棋子所在位置的一列，斜方向和反斜方向没有棋子。怎么判断呢，我们引入bool类型的row[]数组，row[i]=true，表明这一列已经放过棋子了，false表示没有。这个row就解决了列问题，那么斜方向问题怎么解决呢？我们观察一下，题中规定的斜方向，都是符合y=x+b/y=-x+b方程的。b=y-x/b=x+y。同一个b,就是同一条斜线了。我的代码中规定了d[]表示斜方向，ud[]表示反斜方向。比如!d[u+i]，表示x=u,y=i这条斜线上没有棋子，这个b=u+i之前没有出现过。前面就说过，由于斜率一样，所以只要保证这个b不一样，所在斜线就不一样。同理，反斜方向的也是一样，用b=y-x来判断，但是如果y-x<0的话，需要+n偏移一下，统一用ud[i-u+n]。
if(!row[i]&&!d[u+i]&&!ud[i-u+n])表示，对于x=u,y=i这个点，只要同一列，两个斜线处均没有棋子，就符合要求，放上一枚棋子。
其他的就是dfs的基本操作了，还原啦什么的...
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int N = 27; char m[N][N]; bool row[N],d[N],ud[N]; int n; void first() { for(int i = 0 ; i< n ; i ++) for(int j = 0 ; j < n ; j ++) m[i][j]=‘.‘; memset(row,false,sizeof(row)); memset(d,false,sizeof(d)); memset(ud,false,sizeof(ud)); } void dfs(int u) { //cout<<u<<endl; if(u==n) { for(int i = 0 ; i < n ; i ++) { for(int j = 0 ; j < n ;j ++) cout<<m[i][j]; cout<<endl; } cout<<endl; return ; } for(int i = 0 ; i < n ; i++) { if(!row[i]&&!d[u+i]&&!ud[i-u+n]) { m[u][i]=‘Q‘; row[i]=d[u+i]=ud[i-u+n]=true; dfs(u+1); row[i]=d[u+i]=ud[i-u+n]=false; m[u][i]=‘.‘; } } } int main() { while(cin>>n) { first(); dfs(0); } }
另一种比较原始的搜索方式，比较慢：记录皇后数目，如果==n的话，就输出；
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int N = 27; char m[N][N]; bool row[N],d[N],ud[N],urow[N]; int n; void dfs(int x,int y,int s) { //cout<<x<<" "<<y<<" "<<s<<endl; if(y==n) { x++; y=0; } if(x==n) { if(s==n) //这行不能放入if(x==n)里面，因为不管数目达没达到，都要return 掉 { for(int i=0;i<n;i++) puts(m[i]); puts(""); } return ; } if(!row[x]&&!urow[y]&&!d[x+y]&&!ud[y-x+n]) { m[x][y]=‘Q‘; row[x]=urow[y]=d[x+y]=ud[y-x+n]=true; dfs(x,y+1,s+1); m[x][y]=‘.‘; row[x]=urow[y]=d[x+y]=ud[y-x+n]=false; } dfs(x,y+1,s); } int main() { //int n; cin>>n; for(int i=0;i<n;i++) for(int j=0;j<n;j++) m[i][j]=‘.‘; dfs(0,0,0); }
原文：https://www.cnblogs.com/liyexin/p/12680826.html