题目：n?皇后问题是指将 n 个皇后放在 n×n 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上
解法一：对每个格子都进行搜索
#include<iostream> using namespace std; int n; const int N=20; char g[N][N]; //分别表示 行 列 主对角线 副对角线 //主对角线y=x+b,从而b=y-x,下标不能为负,+n,b=y-x+n //副对角线y=-x+b b=x+y bool row[N],col[N],dg[N],udg[N];//初始化默认为false //对每一个格子进行搜索 void dfs(int x,int y,int s ) { //走到最后一列 到下一行搜索 if(y==n) y=0,x++; //走到最后一行 if(x==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); return 0; }
解法二：搜索每一行
//当前皇后所在和行 列 对角线 都不能有其他皇后 #include<iostream> using namespace std; int n; const int N=20; char g[N][N];//存图 //分别存行,主对角线,副对角线 bool col[N],dg[N],udg[N]; void dfs(int 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); return 0; }