qu1.cpp

算法设计与分析中

#include <iostream>
//#include <math.h>
using namespace std;

class Queen{
	friend void Nqueens(int ,int );
public:
	bool Place(int k, int *X);
	void Backtrack(int *X );
	int n, *x;//n表示当前皇后个数，x,当前解
	long sum;//当前已找到的可行方案数
};


/*检查可不可以放置一个新的皇后*/
bool Queen::Place(int k, int *X)
{
 int i;
 i=1;
 for(int j=1;j<k;j++)
  if((X[i]==X[k])||(abs(X[i]-X[k])==abs(i-k)))
   return false;
 return true;
}


/*求解问题的所有解*/
void Nqueens(int n,int *X)
{
 int k,sum=0;
 Queen Q;
 X[1]=0;k=1;
 while(k>0)
 {
  X[k]=X[k]+1;
 
  while((X[k]<=n)&&(!Q.Place(k, X)))
    X[k]=X[k]+1;
 
  if(X[k]<=n)
   if(k==n)
   {
	 sum++;
	 cout<<"第"<<sum<<"种可行的方案:"<<endl;
	
	 for(int i=1;i<=n;i++){
    cout<<"在第"<<i<<"行，把皇后放在第"<<X[i]<<"位。"<<endl;
	 }
    cout<<endl;
	 
   }
   
   else
   {
    k=k+1;
    X[k]=0;
   }
   
  else k--;
 }

cout<<"一共有"<<sum<<"种可能情况，已全部列出！"<<endl;
 
}


void main()
{
 cout<<"|--------------N皇后问题--------------|"<<endl;
 cout<<"|---power by 吴颖颖(20062110010602）--|"<<endl;
 cout<<"|-------------------------------------|"<<endl<<endl;
 int n;
 int *X;
 int i;
  while(i)
  {
   cout<<"请输入皇后的个数:"<<endl;
   cin>>n;
   X=new int[n];
   Nqueens(n,X);
   cout<<"Press<1> to run again"<<endl;
   cout<<"Press<0> to exit"<<endl;
   cin>>i;
  }
 
}