八皇后

八皇后

同在左下->右上对角线上的坐标，行列序号之和为定值。
同在左上->右下对角线上的坐标，行列序号之差为定值。
所以可以用相同下标的数组表示某一对角线是否被占领。

#include<bits/stdc++.h>
using namespace std;

int n,Count=0;
int r[100]={0},c[100]={0},a[100]={0},b[100]={0};//行列 左上->右下对角线，左下->右上对角线 


void dfs(int i){//查找第i行 
	if(i>n){//找到解 
		if(Count<3){
			for(int j=1;j<=n;j++){
		    	printf("%d ",r[j]);
		    }
	    	cout<<endl;
		}
		Count++;
		return ;
	}
	for(int j=1;j<=n;j++){
		if((!c[j])&&(!a[i-j+n])&&(!b[i+j])){
			r[i]=j;//表示i行第j个占领
			c[j]=1;//j列已经占领
			a[i-j+n]=1;
			b[i+j]=1;//两条对角线占领 
			
			dfs(i+1);//找下一行 
			
			//清空标记，寻找下一组解 
			c[j]=0;
			a[i-j+n]=0;
			b[i+j]=0;
		}
	}
}
int main(){
	cin>>n;
	dfs(1);
	cout<<Count<<endl;
	return 0;
}