【算法复习二】八皇后问题 ---- 回溯

一，问题描述

在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

二，分析

采用逐步试探的方式，先从一个方向往前走，能进则进，不能进则退并尝试另外的路径。首先我们来分析一下国际象棋的规则，这些规则能够限制我们的前进，也就是我们前进途中的障碍物。一个皇后q(x,y)能被满足以下条件的皇后q(row,col)吃掉

1）x=row(纵向不能有两个皇后)

2） y=col（横向不能有两个皇后）

3）col + row = y+x;（斜向正方向）

4）col - row = y-x;（斜向反方向）

遇到上述问题之一的时候，说明我们已经遇到了障碍，不能继续向前了。我们需要退回来，尝试其他路径。

我们将棋盘看作是一个8*8的数组，这样可以使用一种蛮干的思路去解决这个问题，这样我们就是在8*8=64个格子中取出8个的组合，C(64,8) = 4426165368,显然这个数非常大，在蛮干的基础上我们可以增加回溯，从第0列开始，我们逐列进行，从第0行到第7行找到一个不受任何已经现有皇后攻击的位置。

前面四列的摆放如上图则 第五列，我们会发现找不到皇后的安全位置

第五列的时候，摆放任何行都会受到上图所示已经存在的皇后的攻击，这时候我们认为我们撞了南墙了，是回头的时候了，我们后退一列，将原来摆放在第四列的皇后

（3，4）拿走，从（3，4）这个位置开始，我们在第四列中寻找下一个安全位置为（7，4），再继续到第五列，发现第五列仍然没有安全位置，回溯到第四列，此时第四列也是一个死胡同了，我们再回溯到第三列，这样前进几步，回退一步，最终直到在第8列上找到一个安全位置（成功）或者第一列已经是死胡同，但是第8列仍然没有找到安全位置为止

总结一下，用回溯的方法解决8皇后问题的步骤为：

1>从第一列开始，为皇后找到安全位置，然后跳到下一列

2>如果在第n列出现死胡同，如果该列为第一列，棋局失败，否则后退到上一列，在进行回溯

3>如果在第8列上找到了安全位置，则棋局成功。

三，源码（精选自网友解答）

回溯法非递归

#include<iostream>
using namespace std;

#define N 8
//N代表皇后数
void queen()
{
	int Count=0;		 //计算总共的解的数量
	int column[N+1];     //column[m]=n 表示第m列，第n行放置了皇后,这里下表并从0开始
	int row[N+1];		 //row[m]=1表示第m行没有皇后，=0表示有皇后
	int b[2*N+1];		 //b[m]=1表示第m条主对角线没有皇后，
	int c[2*N+1];        //c[m]=1表示第m条次对角线没有皇后，=0表示有皇后
	int numQueen=1;		 //计数已经放置的皇后数目，当numQueen=N时候则表示已经完成探测
	int good=1;			 //good=1表示没有发生冲突,good=0表示发生冲突
	
	//初始化这些标记
	for(int j=0;j<N+1;++j)
	{
		row[j]=1; //没有皇后 
	}
	for(int j=0;j<2*N+1;++j)
	{
		b[j]=c[j]=1;
	}
	column[1]=1;
	column[0]=0;          //初始化第一行第一列，第二行第二列放置皇后
	do
	{
		//没有发生冲突，则继续向下探测，增加皇后或者判断当前是否是解
		if(good)
		{
			//当前皇后数是解，打印，继续向下探测
			if(numQueen==N)
			{
				Count++;
				cout<<"找到解"<<endl;
				for(int j=1;j<N+1;++j)
				{
					cout<<j<<"列"<<column[j]<<"行"<<endl;
				}
				//最后一个棋子向下移动,移动到本列最后一个
				while(column[numQueen]==N)
				{
					numQueen--;			//皇后数减1，即列数减1，回溯
					//回溯后将该列以及该列最后一行状态位修改
					//第numQueen列column[numQueen]行处状态位置修改
					row[column[numQueen]]=1;
					b[numQueen+column[numQueen]]=1;
					c[N+numQueen-column[numQueen]]=1;
				}
				column[numQueen]++;		//回溯至上一行，向上一行的下一列继续探测
			}
			//当前不是解，那么继续向下探测
			else
			{
				//改变该位置对应标志
				row[column[numQueen]]=0;
				b[numQueen+column[numQueen]]=0;
				c[N+numQueen-column[numQueen]]=0;
				//本次位置没有发生冲突，也不是正确解，那么就应该向下探测下一列的第一行
				column[++numQueen]=1;
			}
		}
		//如果当前发生了冲突，就在本列继续向下，如果到了本列最后一行，则回溯到上一列
		else
		{
			while(column[numQueen]==N) //到了本列最后一行，还是冲突，那么回溯到上一列
			{
				numQueen--;
				row[column[numQueen]]=1;
				b[numQueen+column[numQueen]]=1;
				c[N+numQueen-column[numQueen]]=1;
			}
			column[numQueen]++;	//发生冲突了，又没有到本列的最后一行，那么在本列继续向下一行探测
		}
		//检测放置了这个位置后是否冲突
		good=row[column[numQueen]]&b[numQueen+column[numQueen]]&c[N+numQueen-column[numQueen]];
	}while(numQueen);
	cout<<N<<"皇后总共找到解："<<Count<<"个"<<endl;
}
int  main()
{
	queen();
	system("pause");
	
	return 0;
}

更牛解答