信息竞赛-1035-n皇后问题

题目描述

【题意】 

会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将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;

}

左斜、右斜值计算以四皇后为例