016.cpp

包含两个文件

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <iostream.h>
//queen_big是我写的第一个程序，速度比钟进的慢了一点，queen是我最新改进的,
//速度比钟进的快了一倍多，但由于我用两个整数分别控制两斜线的冲突，所以现在
//只能求到16皇后(16*2-1<32)，还须改进。
unsigned int queen(unsigned int n);			      //求n皇后的全部解，返回解的个数
unsigned int queen_big(unsigned int n);
void main()
{
	unsigned int n;
	printf("请输入皇后的个数：");
	scanf("%d",&n);	
	if(n==1)
		printf("1皇后问题共有1个解\n");
	else if(n<4)
		printf("%d皇后问题无解\n");
	else if (n<=16)
		printf("%d皇后问题共有%d个解\n",n,queen(n));
	else 
		printf("%d皇后问题共有%d个解\n",n,queen_big(n));
	system("pause");
}

unsigned int queen(unsigned int n)
{
//-------------动态申请数组--------------		

unsigned int *a=new unsigned int [n];
unsigned register int i=0,j=0,k=0,temp=0;

unsigned int *queens=new unsigned int[n];//第i行皇后的位置
unsigned register int x=0,y=0,z=0;

clock_t start_time,end_time;			//时间变量
unsigned register int count=0;			//解的个数
int f;									//某行放皇后是否成功
unsigned int half=(n+1)/2;
unsigned int msk=0 ;
unsigned int length;
length=n*2-1;
msk=(~msk)>>(32-n);
//--------------初始化为0------------------		
for(i=0u;i<n;i++)
{	
		a[i]=0u;
}
for(i=0;i<n;i++)	
	queens[i]=0u;
//---------------求解----------------------
start_time=clock();cout<<"计算开始时间："<<start_time<<endl; //计算开始时间
i=0;
while(1)
{	
	f=0;
	temp=(x | (y >> i) | (z >> (n-i-1))) & msk;
	if (temp==msk) goto retun;
	if((a[0] | a[1]) == 3u<<half-1 || a[0]==1u<<half)
	{	
				goto end;
	}
	for(j=k;j<n;j++)		//从k列开始找
	{
		if(!((1u<<j) & temp))     //第i行的第j列放上皇后	
		{
			a[i]=(1u<<j);
			queens[i]=j;
			x|=a[i];
			y|=(1u)<<(i+j);
			z|=(1u)<<(j+n-i++-1);
			f=1;       //成功
			k=0u;
			break;
		}
	}				
	if(f==0u )          //本行不能放则回朔
	{
retun:	j=queens[--i];		//上一行皇后	
		x&=~a[i];
		y&=~((1u)<<(i+j));
		z&=~((1u)<<(j+n-i-1));
		a[i]=0;		   //皇后位置零
		k=j+1;            //新的开始位置
	}
	else if(f==1 && i==n)    //一个解
	{					
		count++;
	//------删除这个皇后--------
		j=queens[--i];		//上一行皇后
		x&=~a[i];
		y&=~((1u)<<(i+j));
		z&=~((1u)<<(j+n-i-1));
		a[i]=0;
		k=n;            //新位置							
	}
	
}
end :
//计算结束时间
end_time=clock();cout<<"OK!计算已完成,运行时间为"<<end_time-start_time<<"毫秒"<<endl;
delete []a;
delete []queens;
return count*2;
}

unsigned int queen_big(unsigned int n)
{
//-------------动态申请n*n的二维数组--------------		
int *p=new int[n*n];
int **a=new int * [n];
register int i,j,k,x,y,z;
int *queens=new int[n];				//第i行皇后的位置
clock_t start_time,end_time;		//时间变量
register int count=0;						//解的个数
int f;								//某行放皇后是否成功
int cnt=0;							//第一行皇后位置为j时解的个数
int half=(n+1)/2;

for(i=0,j=0;i< n*n ; i+=n,j++)
	a[j]=&p[i];
//--------------初始化为0------------------		
for(i=0;i<n;i++)
{	for(j=0;j<n;j++)
	{	
		a[i][j]=0;
	}
}
for(i=0;i<n;i++)	
	queens[i]=0;
//---------------求解----------------------
start_time=clock();cout<<"计算开始时间："<<start_time<<endl; //计算开始时间

i=0;
k=0;
while(i>=0)
{	
	f=0;
	for(j=k;j<n;j++)		//从k列开始找
	{
		if(a[i][j]==0)     //第i行的第j列放上皇后	
		{
			a[i][j]=-1;
			queens[i]=j;
			if(queens[0]>=half)
			{	
				goto end;
			}
			x=j-1;
			y=j+1;
			z=i+1;
			while((x>=0 || y<=n) && z<n) 
			{
				if (x>=0) a[z][x--]++;
				if(y<n) a[z][y++]++;
				a[z++][j]++;
			}
			i++;
			f=1;       //成功
			k=0;
			break;
		}
	}				
	if(f==0 )          //本行不能放则回朔
	{
		i--;
		if(i<0)
			break;
		j=queens[i];		//上一行皇后
//------删除这个皇后--------	
		x=j-1;
		y=j+1;
		z=i+1;
		while((x>=0 || y<=n) && z<n) 
		{
			if (x>=0) a[z][x--]--;
			if(y<n) a[z][y++]--;
			a[z++][j]--;
		}				
		a[i][j]=0;		   //皇后位置零
		k=j+1;            //新的开始位置
	}
	else if(f==1 && i==n)    //一个解
	{					
		count++;
		if(n%2 && queens[0]==half-1)
			cnt++;
	//------删除这个皇后--------
		i--;	
		a[i][j]=0;
		k=n;            //新位置							
	}
}
end :
//计算结束时间
end_time=clock();cout<<"OK!计算已完成,运行时间为"<<end_time-start_time<<"毫秒"<<endl;
delete []p;
delete []a;
return n%2? count*2-cnt: count*2;
}