題目描述
【題意】?
會下國際象棋的人都很清楚：皇后可以在橫、豎、斜線上不限步數(shù)地吃掉其他棋子。如何將8個皇后放在棋盤上（有8 * 8個方格），使它們誰也不能被吃掉！
這就是著名的八皇后問題。?
【輸入格式】?
一個整數(shù)n（ 1 < = n < = 10 )?
【輸出格式】?
每行輸出對應(yīng)一種方案，按字典序輸出所有方案。每種方案順序輸出皇后所在的列號，相鄰兩數(shù)之間用空格隔開。?
【樣例輸入】?
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));? //每行只能填一個，默認(rèn)為true，可填
memset(row,1,sizeof(row));//每列只能填一個
memset(lft,1,sizeof(lft));//每左斜列只能填一個
memset(rht,1,sizeof(rht));//每右斜列只能填一個 ，
dfs(1);
return 0;
}
