方法一 全排列
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20;
char path[N][N];
bool col[N],dg[N],udg[N];//列 对角线 反对角线上都没有放
int n;
void dfs(int u){//遍历的行 u=0 第 0行 u=1第1行
if(u==n) //u=n时 遍历到下一行 棋盘所有行都遍历完了 输出即可
{
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cout<<path[i][j];
}
cout<<endl;
}
cout<<endl;
return ;
}
for(int i=0;i<n;i++){//i 依次遍历列 摆皇后的位置
if(!col[i]&&!dg[u+i]&&!udg[n-u+i]){
path[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;
path[u][i]='.';
}
}
}
int main(){
cin>>n;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
path[i][j]='.';
}
}
dfs(0);
return 0;
}
方法二 摆与不摆
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10;
char path[N][N];
bool row[N],col[N],dg[N*N],udg[N*N];//列 对角线 反对角线上都没有放
int n;
void dfs(int x,int y,int s){//x y是坐标 s是已经摆在棋盘上的皇后的数量
if(y==n) y=0,x++;
if(x==n){//遍历到了最后一行的下一行
if(s==n){//找出了一种情况
for(int i=0;i<n;i++) puts(path[i]);
puts("");
}
return;//不管有没有找出解 都要回溯
}
//不摆皇后
dfs(x,y+1,s);
//摆皇后
if(!row[x]&&!col[y]&&!dg[x+y]&&!udg[x-y+n]){
path[x][y]='Q';
row[x]=col[y]=dg[x+y]=udg[x-y+n]=true;
dfs(x,y+1,s+1);
path[x][y]='.';
row[x]=col[y]=dg[x+y]=udg[x-y+n]=false;
}
}
int main(){
cin>>n;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
path[i][j]='.';
}
}
dfs(0,0,0);
return 0;
}