学步园

n皇后问题不用多说，基本都知道。回溯算法也不用多说，还是比较简单的，给我的感觉就是不停的找一颗子树或一个排列，并加上判断以回溯。

/*
*	经典回溯问题-----n皇后
*/

#include<iostream>
using namespace std;

#define MAX 1024

int N;
int column[MAX];//每行对应的列值

int sum=0;
bool Place(int row,int col)//判断是否该行可以放置皇后
{
	int i=1;
	for(i;i<row;i++)
	{
		if((column[i]-col)==(i-row)||(column[i]-col)==(row-i)||column[i]==col)
			return false;
	}
	return true;
}

void backTrace(int k)//回溯函数
{
	int i;
	if(k>N)
	{
		cout<<"路径"<<++sum<<"序列为: ";
		for(i=1;i<=N;i++)
			cout<<column[i]<<" ";
		cout<<endl;
	}
	else
	{
		for(i=1;i<=N;i++)
		{
			if(Place(k,i))
			{
				column[k]=i;
				backTrace(k+1);
			}
		}
	}
}
void main()
{
	cout<<"输入皇后数:";
	cin>>N;
	backTrace(1);
}