8皇后问题------回溯法

为了简化，先对4皇后问题进行讨论，对与4皇后问题，先定义一个4x4的棋盘(矩阵)，按照下面规则将4个棋子（皇后）放到棋盘上。

规定：

1、任何两个棋子不同行

2、任何两个棋子不同列

3、任何两个棋子不在用一对角线上

先引入一副图来说明：

（该图为严版教材上的）

对与此问题，刚开始的时候棋盘为空，回溯法的思想是：从该树形结构图的根节点开始，进行先序遍历，到叶子结点时就得到了结果，并输出。在次过程中如果能继续前进则进，否则就退回来，换一条路径。

值得说明的是：这个树形结构图是我们抽象出来的。

就个人而言，此问题可以以行或列为单位，例如就先以行说明，将第一棋子放在第一行，第二个棋子放在第二行.........将最后一个棋子放在最后一行，这样就避免了棋子同行。对与列也可以能有相似的结果。

对与此问题的伪代码：

void Trial1(int i,int n)//采用2维数组存放棋盘，i从第0行开始变化
{
	if(i == n)
		//输出棋盘结果；
	else
	{
		for(int j =0;j<n;j++)//从当前行的第0列到第n-1列以此进行摆放
		{
			if（//如果i行j列能摆放）
				Trial1(i+1,n);//摆放下一行
			//移走i行j列的棋子，防止同一行的棋子重复
		}
	}
}

//////////////////////////////////////////////////////////////////////////////////////////////

#include<iostream>
#include<string>
using namespace std;

const int n =4;	//定义问题规模：4皇后问题
char arr[n][n];//定义棋盘大小
void Print(char str[n][n])
{
	cout<<"----------------------------------------"<<endl;//分隔符 
	for(int i = 0;i<n;i++)
	{
		for(int j =0;j<n;j++)
			cout<<str[i][j]<<" ";
		cout<<endl;
	}
	cout<<"----------------------------------------"<<endl;
}

bool IsOk(int i,int j) 
{
	int row,col;
	//纵向判断     以列为单位就不需要纵向判断 
	for(row =0;row<i;row++)
		if(arr[row][j] == ‘*‘)
			return false;
	for(row =i+1;row<n;row++)
		if(arr[row][j] == ‘*‘)
			return false;
	//横向判断		以行为单位就不需要横向判断 
	for(col=0;col<j;col++) 
		if(arr[i][col] == ‘*‘)
			return false;
	for(col=j+1;col<n;col++)
		if(arr[i][col] == ‘*‘)
			return false;
	//对角判断
	for(row=i-1,col=j-1;row>=0 && col>=0;row--,col--) //左上 
		if(arr[row][col] == ‘*‘)
			return false;
	for(row=i+1,col=j+1;row<n && col<n;row++,col++)//右下 
		if(arr[row][col] == ‘*‘)
			return false;
	for(row=i+1,col=j-1;row<n && col>=0;row++,col--) //左下 
		if(arr[row][col] == ‘*‘)
			return false;
	for(row=i-1,col=j+1;row>=0 && col<n;row--,col++) //右上
		if(arr[row][col] == ‘*‘)
			return false;	 
	return true;
}
void Trial1(int i,int n)//以行为单位摆放 
{
	if(i == n)
	{
		Print(arr);
	}
	else
	{
		for(int j=0;j<n;j++)
		{
			arr[i][j] = ‘*‘;//试探
			if(IsOk(i,j))//判断该位置是否能摆放 
				Trial1(i+1,n);//摆放下一行 
			arr[i][j] = ‘-‘;//设置回原来的状态 
		}
	}
}

void Trial2(int j,int n) //以列为单位摆放
{
	if(j == n)
		Print(arr);//输出棋盘状态
	else
	{
		for(int i=0;i<n;i++)
		{
			arr[i][j] = ‘*‘;
			if(IsOk(i,j))
				Trial2(j+1,n);//摆放下一列 
			arr[i][j] = ‘-‘;//设置回原来的状态 
		}
	} 
}

int main()
{
	
	for(int i=0;i<n;i++)//初始化棋盘 
		for(int j=0;j<n;j++)
			arr[i][j] = ‘-‘;
	Trial2(0,n);//进行回溯遍历 
	return 0;
}

输出结果如下图：

这样就利用回溯法实现了4皇后问题，当然对于8皇后的问题，只要在设置棋盘的大小时，将n设置为8，此问题就是8皇后问题了！

8皇后问题------回溯法,布布扣,bubuko.com

8皇后问题------回溯法

原文：http://blog.csdn.net/a812073479/article/details/21180677