nhou.txt

n皇后问题的源代码以及关于n皇后问题的说明

#include<iostream.h>
#include<math.h>
class Queen
{
	friend int nQueen(int);
	private:
		bool Place(int k);
		void Backtrack(int t);
		int n,
			*x;
		long sum;
};

bool Queen::Place(int k)
{
	for(int j=1;j<k;j++)
		if((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k]))
			return false;
	return true;
}

void Queen::Backtrack(int t)
{
	if(t>n)
		sum++;
	else
		for(int i=1;i<=n;i++)
		{	
			x[t]=i;
			if(Place(t))
				Backtrack(t+1);
		}
}

int nQueen(int n)
{
	Queen X;
	//初始化 X
	X.n=n;
	X.sum=0;
	int *p=new int[n+1];
	for(int i=0;i<=n;i++)
		p[i]=0;
	X.x=p;
	X.Backtrack(1);
	delete []p;
	return X.sum;
}

void main()
{
	int n;
	int sum;
	cout<<"请输入n的值:\n";
	cin>>n;
	sum=nQueen(n);
	cout<<"可行解的个数为:"<<sum<<endl;
}