n皇后.cpp

c++ n皇后问题的原代码

#include <iostream.h>
#include <math.h>
class queen
{
	friend int nqueen(int);
private: 
	bool place(int k);
	void backtrack(int t);
	int n;//queen number
	int *x;//current solve
	long sum;//the number of all current solve
};
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++;
		for(int j=1;j<=n;j++)
			cout<<x[j]<<"  ";
		cout<<endl;
	}
	else
		for(int i=1;i<=n;i++)
		{
			x[t]=i;//cout<<t<<x[t]<<endl;
			if(place(t)) {backtrack(t+1);}
			//else if(t==n) t--;
		}
}
int nqueen(int n)
{
	queen X;//orginal or initial
	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 a,b;
	cout<<"please int the number of queen!!   ";
	cin>>a;cout<<endl;
	b=nqueen(a);
	cout<<"The number of all solve is  "<<b<<endl;
}