queen3.cpp

皇后问题

#include     <iostream.h>
#include     <fstream.h>
#include      <cstdlib>
#include     <time.h>
const    unsigned long    maxshort=65536L;
const    unsigned long    multiplier=1194211693L;
const    unsigned long    adder=12345L;

class  RandomNumber
{ 
private:
        unsigned   long    randSeed;
public:
	    RandomNumber(unsigned    long   s=0);
		unsigned  short  Random(unsigned   long   n);
		double   fRandom(void);
};
RandomNumber::RandomNumber(unsigned  long  s)
{
	if(s==0)  
		randSeed=time(0);
	else  
		randSeed=s;
}
unsigned   short   RandomNumber::Random(unsigned   long  n)
{     
	randSeed=multiplier*randSeed+adder;
	return  (unsigned short)((randSeed>>16) % n);
}
double RandomNumber::fRandom(void)
{
	return    Random(maxshort)/double(maxshort);
}

int  NQueen(int n,int*  &bestx){
    RandomNumber rnd;
	int **A=new  int *[n+1];
	for(int i=0;i<=n;i++)
		A[i]=new  int[n+1];
	int  best=n;
	int *b=new int[n+1];
	b[0]=0;
	int lenb=n;
	int *c=new int[n+1];
	for(i=0;i<=n;i++)
		c[i]=0;
	int lenc=0;
	int row=0;
	int col=0;
	int result=0;
	int index=0;
    int  aa=0;
	int  bb=0;
	int  *x=new  int[n+1];
 
  for(int  k=1;k<=20000;k++){  
      for(i=0;i<=n;i++)
		   for(int  j=n;j>=1;j--)
			   A[i][j]=0;
	  for(i=0;i<=n;i++)
	     x[i]=0;
	  result=0;
	  for(i=n;i>=1;i--)
		  b[i]=i;
	  lenb=n;
	  lenc=0;
	

	   while(lenb>=1){
             int index=rnd.Random(lenb)+1;
	         row=b[index];
	         int temp=b[lenb];
	         b[lenb]=b[index];
	         b[index]=temp;
             lenb--;
	 
	         lenc=0;
	         for(int i=1;i<=n;i++)
		        if(A[row][i]==0)
			       c[++lenc]=i;

	         if(lenc>0){
		        index=rnd.Random(lenc)+1;
                col=c[index]; 
			    x[row]=col;
			    result++;
			    for(int  k=1;k<=n;k++)
				    A[row][k]=1;
			    for(k=1;k<=n;k++)
				    A[k][col]=1;

			    aa=row;
			    bb=col;
			    while(aa>=1 && bb<=n){
				      A[aa][bb]=1;
				      aa--;
				      bb++;
				}
			    aa=row;
			    bb=col;
			    while(bb>=1 && aa<=n){
				     A[aa][bb]=1;
				     aa++;
				     bb--;
				}
			    aa=row;
			    bb=col;
			    while(aa>=1 && bb>=1){
				     A[aa][bb]=1;
				     aa--;
				     bb--;
				}
			    aa=row;
			    bb=col;
			    while(bb<=n && aa<=n){
				     A[aa][bb]=1;
				     aa++;
				     bb++;
				}
			   A[row][col]=2;
			 } 	   
	   }
	   if(best>result){
		  best=result;
		  for(int i=1;i<=n;i++)
			  bestx[i]=x[i];
	   }
  }
    delete[]  b;
	delete[]  c;
	delete[]  x;
	delete[]  A;
	return   best;
}

//****************************************************************
//主程序开始
void   main(){
	ifstream   fin("input.txt");//定义输入数据流
	ofstream   fout("output.txt");//定义输出数据流
	int   n=0;
	fin>>n;//读入数据
	if(n==0)//若数据为0，则返回
		return;
   int   *bestx=new  int[n+1];
   for(int i=0;i<=n;i++)
	    bestx[i]=0;
   int   result=NQueen(n,bestx);
   fout<<result<<endl;
   for(i=1;i<=n;i++)
	   fout<<bestx[i]<<' ';
   cout<<endl;
   cout<<result<<endl;

}