作者 ： 卿笃军

本文讨论了八皇后问题的三种解决方案：

一、枚举法

二、回溯法（递归版）

三、回溯法（非递归版）

本来这些代码是以前编写好的，没有发表，由于最近又学习到了八皇后问题，自己整理了一下发表了出来！

首先、说明一下何为八皇后问题，我也不去谷歌了，直接简单的说明一下：

八皇后问题，就是在一个8*8的平面棋盘上，要求你摆放8个棋子，要求：这8个棋子不能有2个在同一行，也不能有2个在同一列，同时一条斜线上面也不能有2个~~~~

比如：4*4的棋盘，你可以这样摆放（4皇后问题）：

以上图为参照，我们分析一下，要使棋子不冲突，那算法要如何写？

我们将二维数组降为一维数组，并用下面这种方式来标记棋子：

示例： a[1] = 2 ，表示第1列第2行有旗子。

a[2] = 4 ， 表示第2列第4行有旗子。

a[3] = 1 ， 表示第3列第1行有旗子。

a[4] = 3 ，表示第4列第3行有旗子。

好，接着分析冲突算法该如何编写：（冲突算法：就是用来判断落棋子位置是否与其它棋子冲突）

可能出现的几种冲突情况：

1）第一行有两个棋子，应该是这样表示：a[1] = 1, a[2] = 1,表示第一列和第二列的第一行都有棋子（暂且不考虑3,4列）。

2）主对角线上有2个棋子，应该是这样表示：a[1] = 2, a[2] = 3,表示第一列第二行，第二列第三行位置上有棋子。

3）次对角线上有2个棋子，应该是这样表示：a[3] = 4, a[4] = 3,表示第三列第四行，第四列第三行位置上有棋子。

注意：不可能在列上出现冲突，因为，我们是按列摆放的。即：第一列上摆放一个，然后在第二列上摆放.....第三列，每列摆放一个棋子。

下面编写代码：（强调：下面出现的不管是i还是j表示的都是列：第i列，第j列）

行冲突：

首先，检测第一行的1-8列，是否冲突。然后检测第二行...........当然其实第一列不需要检测（因为摆放第一个棋子的时候，棋盘上还没有棋子，不可能冲突）

for (int i = 1; i <= 8; ++i)  //检测1~8行
{
	for (int j = 1; j <= 8; ++j) //检测1~8列
	{
		if (a[i] == a[j])
			return "冲突";
	}
}
return "不冲突";

这里稍微用数学分析一下，用i,j表示当前正在检测的两列（i外层for循环,j内层for循环），那么a[i] ，a[j] 的值就分别表示当前检测列棋子摆放的位置即行（每列只有1个棋子）。

如果两个棋子对角线冲突（正反对角线冲突），则必然有：

转化为代码：

for (int i = 1; i <= 8; ++i)  //检测1~8行
{
	for (int j = 1; j <= 8; ++j) //检测1~8列
	{
		if ((a[i] - a[j] == i - j)  || (a[i] - a[j] == j - i))  //对角线冲突
			return "冲突";
	}
}
return "不冲突";

//位置冲突算法 
bool Chongtu(int a[], int n)//a[]位置数组，n皇后个数 
{
	for (int i = 2; i <= n; ++i)//i：位置 
		for (int j = 1; j <= i-1; ++j)//j：位置 
			if ((a[i] == a[j]) || (abs(a[i]-a[j]) == i-j))//1：在一行；2：在对角线上 
				return false;   //冲突 
	return true;//不冲突 
}

好了，该说明的都说明了，现在编写第一个八皇后代码~~~~

枚举法：

思想：八重枚举，枚举出所以摆放的情况（不管合理不合理），然后到第八层for里面判断当前枚举出来的情况是否合理~~~~

#include <stdio.h>
#include <math.h>
//位置冲突算法 
bool Chongtu(int a[], int n)//a[]位置数组，n皇后个数 
{
	int i = 0, j = 0;

	for (i = 2; i <= n; ++i)//i：位置 
		for (j = 1; j <= i-1; ++j)//j：位置 
			if ((a[i] == a[j]) || (abs(a[i]-a[j]) == i-j))//1：在一行；2：在对角线上 
				return false;   //冲突 
	return true;//不冲突 
}
//八皇后：枚举算法 
void Queens8()
{
	int a[9] = {0}; //用于记录皇后位置：(第0行0列我们不用)。如：a[3] = 4;表示第3列第4行位置有皇后
	int i = 0,count = 0;  //用于计数 

	for (a[1] = 1; a[1] <= 8; ++a[1])
		for (a[2] = 1; a[2] <= 8; ++a[2])
			for (a[3] = 1; a[3] <= 8; ++a[3])
				for (a[4] = 1; a[4] <= 8; ++a[4])
					for (a[5] = 1; a[5] <= 8; ++a[5])
						for (a[6] = 1; a[6] <= 8; ++a[6])
							for (a[7] = 1; a[7] <= 8; ++a[7])
								for (a[8] = 1; a[8] <= 8; ++a[8])
								{
									if (!Chongtu(a,8))//如果冲突，则继续枚举 
										continue;
									else
									{
										printf("第%d情况：",++count);
										for (i = 1; i <= 8; ++i)
											printf("%d ",a[i]);//打印某种情况 
										printf("\n");
									}
								}
}
//主函数 
int main()
{
	Queens8();

	return 0;
}

#include <stdio.h>
#include <math.h>

int a[9] = {0};
int n = 8, count = 0;

//位置冲突算法 
bool Chongtu(int a[], int n)//a[]位置数组，n皇后个数 
{
	int i = 0, j = 0;

	for (i = 2; i <= n; ++i)//i：位置 
		for (j = 1; j <= i-1; ++j)//j：位置 
			if ((a[i] == a[j]) || (abs(a[i]-a[j]) == i-j))//1：在一行；2：在对角线上 
				return false;   //冲突 
	return true;//不冲突 
}

//八皇后问题：回溯算法（递归版） 
void Queens8(int k) //参数k：递归摆放第k个皇后 
{
	int i = 0;

	if (k > n)      //k>n：即k>8表示最后一个皇后摆放完毕 
	{
		printf("第%d种情况：",++count);
		for (i = 1; i <= n; ++i)
			printf("%d ",a[i]);//打印情况 
		printf("\n");
	}
	else   //8个皇后未全部摆放完毕        
	{
		for (i = 1; i <= n; ++i)//摆放第k个皇后时（转下一行） 
		{       //依次从列顶端开始搜索，一直到列底端，直到找到合适位置,如果未找到，自动返回上层递归(回溯) 
			a[k] = i;               
			if (Chongtu(a,k))//不冲突 
				Queens8(k+1);//递归摆放下一个皇后
		}
	}
	return;
}

//主函数 
int main()
{
	Queens8(1);//参数1：表示摆放第1个皇后 

	return 0;
} 

#include <stdio.h>
#include <math.h>

//位置冲突算法 
bool Chongtu(int a[], int n)//a[]位置数组，n皇后个数 
{
	int i = 0, j = 0;

	for (i = 2; i <= n; ++i)//i：位置 
		for (j = 1; j <= i-1; ++j)//j：位置 
			if ((a[i] == a[j]) || (abs(a[i]-a[j]) == i-j))//1：在一行；2：在对角线上 
				return false;   //冲突 
	return true;//不冲突 
}

//八皇后问题：回溯法（非递归） 
void Queens8()
{
	int n = 8;        //8个皇后 
	int count = 0;    //记录当前第几情况 
	int a[9] = {0};   //存放皇后位置，如：a[2] = 4;表示第2列第4行有一个皇后（a[0]不用） 
	int i = 0,k = 1;  //初始化k为第一列 

	a[1] = 0;         //初始化a[1] = 0 
	
	while (k > 0)     //k==0时：表示摆放第1个皇后就超过了列底部（即已经找完所有情况） 
	{
		a[k] += 1;    //a[k]位置，摆放一个皇后 
		while ((a[k] <= n) && (!Chongtu(a,k)))//如果a[k]（即皇后摆放位置）没有到列最底部，且摆放冲突。 
			a[k] += 1;//将皇后列下移一位 
		if (a[k] <= n)//皇后摆放位置没有到达列最底部 
		{
			if (k == n)//k==n表示，8列皇后全部摆放完毕 
			{
				printf("第%d种情况：",++count);
				for (i = 1; i <= n; ++i)//打印情况 
					printf("%d ",a[i]);
				printf("\n");
			}
			else      //皇后还未摆放完毕 
			{
				k += 1;    //继续摆放下一列 
				a[k] = 0;  //此行初始化a[k] = 0;表示第k列，从第一行开始摆放皇后 
			}
		}
		else  //回溯：当a[k]>8进入else,表示在第k列中没有找到合适的摆放位置 
			k -= 1;//回溯到k-1步：k表示第几个皇后，a[k]表示第k个皇后摆放的位置 
	}
	return;
}

//主函数 
int main()
{
	Queens8();

	return 0;
}