#include<iostream.h>
#include<math.h>
#include<stdio.h>

#include<time.h>

const unsigned long maxshort=65536L;
const unsigned long multiplier=1194211693L;
const unsigned long adder=12345L;



//產(chǎn)生種子
unsigned long randSeed;
 void RandomNumber(unsigned long s)
{
  if(s==0)
	  randSeed=time(0);
  else
	  randSeed=s;
  
}

//產(chǎn)生0:n-1之間的隨機數(shù)
unsigned short Random(unsigned long n)
{
	
 randSeed=multiplier *randSeed+adder;
 return(unsigned short)((randSeed>>16)%n);
}



class Queen
{
    friend void nQueen(int);
    private:
	       bool Place(int k);
	       void Backtrack(int t);
	       int n,*x,*y;
		   bool QueensLV(int stopVegas);
	      
};

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)
 {
	 for(int i=1;i<=n;i++)
		 y[i]=x[i];
         return;
 }
 else
 	 for(int i=1;i<=n;i++)
	 {
		 x[t]=i;
	     if(Place(t))
		 Backtrack(t+1);
	 }

}


bool Queen::QueensLV(int stopVegas)
{

 int k=1;
 int count=1;
 while((k<=stopVegas)&&(count>0))
 {
  count=0;
  int j=0;
	  for(int i=1;i<=n;i++)
	  {
	   x[k]=i;
	   if(Place(k))
		   if(Random(++count)==0) 
			   j=i;
	  }
	  if(count>0)
		  x[k++]=j;
 }
 return (count>0);
}

void nQueen(int n)
{
 Queen X;
 X.n=n;

 int *q=new int[n+1];
 int *p=new int[n+1];
 for(int i=0;i<=n;i++)
 {
	 p[i]=0;
     q[i]=0;
 }
 X.y=p;
 X.x=q;
 int stop=3;
 while(!X.QueensLV(stop));
 X.Backtrack(stop+1);
for( i=1;i<=n;i++)
cout<<p[i]<<" ";
cout<<endl;
 delete[] p;
 delete[] q;

}
void main()
{
 int n;
 printf("******************************************\n");
 printf("*                                        *\n");
 printf("*   暨南大學(xué) 計算機軟件與理論專業(yè) 陳泓坤 *\n");
 printf("*                                        *\n");
 printf("*          學(xué)號:0634064015               *\n");
 printf("*                                        *\n");
 printf("*        回溯法求解n皇后問題             *\n");
 printf("******************************************\n\n\n");
 cout<<"請輸入皇后個數(shù):";
 cin>>n;
nQueen(n);


 
 

}