题目描述
【题意】
会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上（有8 * 8个方格），使它们谁也不能被吃掉！
这就是著名的八皇后问题。
【输入格式】
一个整数n（ 1 < = n < = 10 )
【输出格式】
每行输出对应一种方案，按字典序输出所有方案。每种方案顺序输出皇后所在的列号，相邻两数之间用空格隔开。
【样例输入】
4
【样例输出】
2 4 1 3
3 1 4 2
代码：
#include<cstdio>
#include<cstring>
//左斜从[1,1] 右斜从[n,1]
using namespace std;
int n,r,a[110];
bool col[110],row[110],lft[230],rht[230];
void dfs(int k){
if(k==n+1){
for(int i=1;i<=n;i++) printf("%d ",a[i]);
printf("\n");
}else{
for(int j=1;j<=n;j++){
if(row[k]&&col[j]&&lft[k+j-1]&&rht[j-k+n]){
a[k]=j;
row[k]=0;col[j]=0;lft[k+j-1]=0;rht[j-k+n]=0;
dfs(k+1);
a[k]=0;
row[k]=1;col[j]=1;lft[k+j-1]=1;rht[j-k+n]=1;
}
}
}
}
int main(){
scanf("%d",&n);
memset(col,1,sizeof(col)); //每行只能填一个，默认为true，可填
memset(row,1,sizeof(row));//每列只能填一个
memset(lft,1,sizeof(lft));//每左斜列只能填一个
memset(rht,1,sizeof(rht));//每右斜列只能填一个 ，
dfs(1);
return 0;
}
