八皇后问题：古老著名的回溯算法典型案例及相关问题探究

八皇后问题

八皇后问题是一个古老且著名的问题，它是回溯算法的典型案例。这个问题是国际西洋棋棋手马克斯·贝瑟尔在 1848 年提出的。要在 8×8 格的国际象棋上摆放八个皇后，且让它们不能互相攻击，也就是任意两个皇后都不能处于同一行、同一列或同一斜线上，需要探究有多少种摆法。高斯认为有 76 种方案。1854 年在柏林的象棋杂志上，不同的作者发表了 40 种不同的解。后来，有人通过图论的方法解出了 92 种结果。计算机发明之后，有多种计算机语言能够解决此问题。

问题条件：任两个皇后都不能处于同一条横行、纵行或斜线上。

八皇后问题能够推广成为更为普遍的 n 皇后摆放问题。在这种情况下，棋盘的大小变为 n1 乘以 n1，同时皇后的个数也变为 n2。并且只有当 n2 等于 1 或者 n1 大于或等于 4 时，这个问题才会有解。

解决基本思想：递归

程序基本模块：

主函数没什么特别需要说明的内容。

1、判断模块conflict()：

2、递归模块queens()：

全部代码： 理解版：

#include
#include
定义一个函数 conflict，该函数接收一个整型指针 state、一个整型 nextx 和一个整型 nexty 作为参数。
{//判断准备放下的后是否与之前的后有冲突
	//state是储存之前皇后的位置数组，
	//nextx，nexty分别代表准备放下皇后的列和行
判断的条件为不同列，也就是（state[i] - nextx）不等于 0 。
	//不同行：由于nexty必定大于已有的行数，则必定不同行
	//不在对角线上，先写出已知(x0,y0)的对角线方程：
y - y0 等于正的或负的 (x - x0)；这意味着 (nextx, nexty) 不在该直线上。
	//综上，条件如下：
	for (int i = 0; i < nexty; i++){
		if ((abs(state[i] - nextx) == (nexty - i)) || \
			(abs(state[i] - nextx) == 0))
			return 1;
	}
	return 0;
}
int queens(int num, int*state,int len)
{
	if (num - len == 1){//判断是否到最后一个皇后，是则：
		for (int position = 0; position < num; position++){
			//遍历位置
			if (!conflict(state, position, len)){//判断是否有冲突
				state[len] = position;//没有冲突，记录位置到state
				printf("当前state:");
				for (int i = 0; i <= len; i++){
					printf("%d", state[i]);//输出
				}
				printf("\n");
				return 1;
			}
		}	
		return 0;
	}
	else{//不是最后一个皇后则：
		for (int position = 0; position < num; position++){
			//遍历位置
			if (!conflict(state, position, len)){
				//判断是否有冲突，没有冲突则：
				//记录新皇后位置到state
				state[len] = position;
				if (queens(num, state, len + 1)){
				//进入下次递归，并判断返回值
				}
				else{
				//如果下个皇后遍历全部位置都有冲突，返回到本层
				//将本层的皇后位置+1，即继续遍历本层
					continue;
				}
			}
			else
				//若本层当前位置有冲突，则继续遍历
				continue;
		}
		return 0;
	}
}
void main()
{
	int *state[8];
	queens(8, state, 0);
	system("pause");
}

2.精简版：

#include
#include
定义一个名为 conflict 的函数，该函数接收一个整型指针 state、一个整型 nextx 和一个整型 nexty 作为参数。
{                                                                               
    for(int i=0;i