最近因为接触了最短路径问题所以开始了解dfs和bfs，从dfs开始就是熟悉的八皇后问题。

大家都很清楚八皇后问题主要是将八个皇后分在一个8*8的格子内，然后每个皇后所在的行、列、主对角线和副对角线都不能有其他皇后存在，故这就需要采用一个个判断问题了。

也许有些人想从二维数组方面入手。但是想到的是，每次将某个皇后位置定下后，对其所在的行、列、主对角线和副对角线都要置false，对其所在行、列、主对角线和副对角线都置false将提高复杂度，而且当某次放置所有皇后并不成立，那么就要对二维数组全部置true后重新开始（对第一次放的皇后位置置false），这将十分麻烦。

所以我们可以从其内部入手。

我们定义一个一位数组，默认从行开始，这样就可以避免行冲突，然后将一位数组值置为列值，如果某两个不同行的列值相同，则其列冲突，不符合。

那么对于主对角线和副对角线呢

我们这里介绍一个小技巧，

 1  2  3  4
 5  6  7  8
 9 10 11 12
13 14 15 16

如上是一个4*4的矩阵，

我们可以得知如果一些数字在一条主对角线上，其行列之差相同，

如1（1,1） 6（2,2） 11（3,3） 12（4,4）行列之差均为0，所以我们可以在判断时这样写

judge[x]-x = judge[y]-y，这可以作为一个判断条件

 

那么相应的副对角线，你会发现一条副对角线的所有位置行列之和相同

如4（1,4）7（2,3） 10（3,2） 13（4,1）行列之和均为5，所以这时我们这么判断

judge[x]+x = judge[y]+y，这同样也是一个判断条件

 

这时候也许你会疑惑怎么解决判断的范围问题，那么我们只要判断当前行的上面所有行即可

即我们判断时范围限制在current前所有行。

下面是一个八皇后的总放置方式的代码

#include<stdio.h>
int n = 8;
int judge[8];
int total;
int check(int cur){
	for(int i = 0; i < cur; i++)
		if(judge[i] == judge[cur] || judge[i]+i == judge[cur]+cur || judge[i]-i == judge[cur]-cur) //依次是列、副对角线、主对角线的判断 
			return 0;
	return 1;
}
void dfs(int cur){
	if(cur == n)
		total++;//因为我们是判断0~7的，如果到达了n=8，即所有放置完成。此种方式合适 
	else{
		for(int i = 0; i < n; i++){
			judge[cur] = i; //先判断cur行i列 ，每次cur行放置时，都是从其0列开始的。 
			if(check(cur))
				dfs(cur+1);//如果符合条件，则向下继续放置 
		}
	}
	 
}
int main()
{
	dfs(0);
	printf("%d\n", total);
	return 0;
}

 

 

那么下一个问题就是，我们该如何输出这么些放置呢，输出所有的排列矩阵，排列皇后即输出1，否则输出0

代码及注释：

#include<stdio.h>
int n = 8;
int judge[9];
int total;
int out[9][9];//输出数组 
int check(int cur){
	for(int i = 0; i < cur; i++)
		if(judge[i] == judge[cur] || judge[i]+i == judge[cur]+cur || judge[i]-i == judge[cur]-cur)
			return 0;
	return 1;
}
void dfs(int cur){
	if(cur == n){ 
		total++; 
		printf("No.%d\n", total); //符合条件即输出 
		for(int i = 0; i < n; i++){ 
			for(int j = 0; j < n; j++)
				printf("%d ", out[i][j]);
			printf("\n");
		}
		printf("\n");
	} 
	else{
		for(int i = 0; i < n; i++){
			judge[cur] = i; 
			if(check(cur) && out[cur][i] != 1){
				out[cur][i] = 1; //符合条件的位置置1 
				dfs(cur+1);
				out[cur][i] = 0; //递归结束后依次置0 
			} 
		}
	}
	 
}
int main()
{
	dfs(0);
	return 0;
}

输出每行所放置的皇后列代码：

#include<stdio.h>
int n = 8;
int judge[9];
int total;
int out[9][9];//输出数组 
int check(int cur){
	for(int i = 0; i < cur; i++)
		if(judge[i] == judge[cur] || judge[i]+i == judge[cur]+cur || judge[i]-i == judge[cur]-cur)
			return 0;
	return 1;
}
void dfs(int cur){
	if(cur == n){ 
		total++; 
		printf("No.%d\n", total); //符合条件即输出 
		for(int i = 0; i < n; i++){ 
			for(int j = 0; j < n; j++){ 
				if(out[i][j] == 1)
					printf("%d ", j+1);
				else
					printf("%d ", out[i][j]);
			} 
			printf("\n");
		}
		printf("\n");
	} 
	else{
		for(int i = 0; i < n; i++){
			judge[cur] = i; 
			if(check(cur) && out[cur][i] != 1){
				out[cur][i] = 1; //符合条件的位置置1 
				dfs(cur+1);
				out[cur][i] = 0; //递归结束后依次置0 
			} 
		}
	}
	 
}
int main()
{
	dfs(0);
	return 0;
}