皇后问题递归.cpp

算法设计与分析 第五章王晓东版的 回溯法的0-1背包问题

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

};



int nQueen(int n)
{
	QUEEN 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;
	
}

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++;
	cout << "n皇后问题的第"<<sum<<"个"<<"可行解的坐标为:"<<endl;
	for(t=1;t<=n;t++)
	cout <<"( "<<t<<","<<x[t]<<")"<<endl;
	cout << "********"<<endl;}
	
		else
		for(int i=1;i<=n;i++)
		{
			x[t]=i;
		if(Place(t))
			Backtrack(t+1);
}
}
		void  main()
		{   int n;
			cout <<"***************N 皇后问题*************** "<<endl;
			cout << endl;
	        cout <<"请输入皇后的个数 n:  "<<endl;
			cin>>n;
		  cout<<nQueen( n)<<endl;
            

            cout <<"***************N 皇后问题结束*************"<<endl;
		}