递归法解决N皇后问题

                                                                            N皇后问题

题目：

在一个n*n的棋盘上面放置n个皇后，要使得任意两个皇后之间不能相互攻击，规则是任意两个皇后处在同一行，同一列或者同一斜线的位置上时，能够相互攻击，皇后可以走任意步。

分析

通过分析题目可以知道，若使任意两个皇后都不能互相攻击，那么就必须使得任意两个皇后不能处在同一行，同一列，同一斜线即可（隐藏条件，皇后不能处在同一点），我们可以把棋盘看成一个n*n的等差坐标系，假设当一个皇后放在了（i，j）位置上时，那么i行，j列上的所有左边都不能再放置新的皇后，同时再所有的经过（i，j）点的斜线也是不能够放置皇后，行和列好解决，关键是如何解决斜线，因为再坐标系当中，任意点与其同一斜线上的点所构成的图形均为正方形，该斜线即为正方形的对角线，那么根据正方形的性质可知，其四条边相等，所以可以得到（记斜线上的某一点为（x，y））：（x-i）的绝对值=（y-j）的绝对值，所以这是能否放置皇后的充要条件。

#include<cstdio>
#include<cmath>
int sum=0;
bool pd(int i,int *a) {
	if(i==0)
		return true;//刚开始棋盘没有任何棋子，所以条件都满足
	for(int k=0; k<i; k++) {
		//不在同一列，同一对角线，因为使用了一维数组，每一行只占用一个位置，所以不在同一行隐含在了里面
		if((a[k]==a[i])||(abs(i-k)==abs(a[i]-a[k])))
			return false;
	}
	//条件满足，返回true代表当前位置可以放置
	return true;
}
//输出
void print(int *a,int n) {
	for(int i=0; i<n; i++) {
		for(int j=0; j<n; j++) {
			if(j==a[i])
				//一维数组中的数据代表再第几列，一维数组的下表代表在第几行
				printf("@ ");//打印皇后棋子
			else
				printf("# ");//打印棋盘
		}
		printf("\n");
	}
	printf("\n");
}
int qj(int i,int *a,int n) {
	for(int j=0; j<n; j++) {
		a[i]=j;//当前位置放置棋子
		if(pd(i,a)) {//判断是否满足
			if(i==(n-1)) {//判断是否是棋盘的最后一行
				print(a,n);//是的话，输出当前结果
				sum++;//解法总数+1
			} else
				qj(i+1,a,n);//如果不是最后一行，则行数+1，递归继续执行
		} else
			//不满足像左移动一位，接着判断，因为一维数组是用来存放列左边的，所以j+1代表列+1
			continue;
	}
}
int main() {
	int n;
	scanf("%d",&n);
	int a[n];//定义一维数组存放皇后的列坐标 
	qj(0,a,n);
	printf("%d\n",sum);
}