n 皇后问题非递归.cpp

来自「算法设计与分析 第五章王晓东版的 回溯法的0-1背包问题」· C++ 代码 · 共 84 行

#include<iostream.h>
#include "math.h"
class QUEEN  
{
public:
	
	
	friend int nQueen(int);
	
private:
	bool Place(int k);
	void Backtrack(void);
	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();
	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(void)
{
	x[1]=0;
	int k=1;
	while (k >0)
	{
	x[k]+=1;
	while ((x[k]<=n)&&!(Place(k))) x[k]+=1;
	if (x[k]<=n)  
	{  if (k==n)
		{sum++;

	    cout << "n皇后问题的第"<<sum<<"个"<<"可行解的坐标为:"<<endl;
	     for(k=1;k<=n;k++)
	     cout <<"( "<<k<<","<<x[k]<<")"<<endl;
	     cout << "********"<<endl;
	}
	   else
		{
		k++;
		x[k]=0;
	   }}

		else k--;
		
}

	    
}
		void main()
		{
		int n;
			cout <<"***************N 皇后问题非递归*************** "<<endl;
			cout << endl;
	        cout <<"请输入皇后的个数 n:  "<<endl;
			cin>>n;
		  cout<<nQueen( n)<<endl;
            

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