007.cpp

包含两个文件

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


int *qx,*qy,*qr,*ql,*line,quse=0;
int pd(int ,int);


void main()
{
   char k;
   printf(" 2005级王恩涛 求解n皇后的全部解\n\n");
   cout<<" 13 皇后用    500毫秒---73712个解"<<endl;
   cout<<" 14 皇后用   2734毫秒---365594个解"<<endl;
   cout<<" 15 皇后用  18922毫秒---2279184个解"<<endl;
   cout<<" 16 皇后用 122281毫秒---14772512个解"<<endl;
   cout<<" 17 皇后用 958328毫秒---95815104个解"<<endl;
   do   
   {
	quse=0;  // 开始时皇后为0
	int i,n,key=1;
	unsigned long int t=0,tt=0;
	cout<<"\n请输入皇后的个数n=";
	cin>>n;
	cout<<endl;
	qx=new int[n+2];//用来存储皇后所在的列数，
	qy=new int[n+2];//用来存储皇后所在的行数
	qr=new int[2*n+2];//用来标记皇后的右对角线是否攻击
	ql=new int[2*n+2];//用来标记皇后的左对角线是否攻击
	line=new int[n+2];//用来标记皇后的列是否攻击 。     值为0代表不攻击 值为1代表攻击
	
	for(i=0;i<n+2;i++)
	{
		qx[i]=-1;		qy[i]=0;		line[i]=0;  //初始化 
		
	}
	for(i=0;i<2*n+2;i++)
	{
		ql[i]=0;
		qr[i]=0;  //初始化 	 
	}

   
	
	/*下面利用对称法，如果皇后数是偶数则只需计算在第一行的前一半位置放皇后，然后乘2就得
	  到了全部的解，如果是奇数则先计算出第一行的前(n-1)/2个位置放皇后的方法t，然后再计算第(n-1)/2+1个
	  位置放皇后的方法tt,那么 t*2+tt就是所求的解 */
	 clock_t start_time,end_time; //时间变量
                start_time=clock(); 
	while(quse>=0 && qx[0]<n/2)  
		{
			key=1;
			if(qx[quse]<n-1)  //如果皇后的列数不是最后一列
			{
				for(i=qx[quse]+1;i<n;i++)  //从下一行开始判断位置是否冲突
				{
					if(line[i]==0)   // 判断这个位置的列上有皇后没有？
					   if(ql[n-1+quse-i]==0) // 判断这个位置的左对角线上有皇后没有？
						  if(qr[quse+i]==0)// 判断这个位置的右对角线上有皇后没有？
						  {   //放入新皇后
				 			  qx[quse]=i;  // 该皇后的列为i
						      qy[quse]=quse;// 该皇后的行为i
						      ql[n-1+quse-i]=1; // 将该皇后的左对角线标记为1
						      qr[quse+i]=1;// 将该皇后的右对角线标记为1
						      line[i]=1;// 将该皇后的列标记为1
						      quse++;//皇后数加1
					          key=0; //分配成功
						      break;
						  }
				}
			}				
			if(key) //位置冲突，没有放入皇后，回朔到上一个皇后
			{
				qx[quse]=-1;
				quse--;
				ql[n-1+quse-qx[quse]]=0; //将这个皇后的位置的左对角线标记为0
				qr[qy[quse]+qx[quse]]=0;//将这个皇后的位置的右对角线标记为0
				line[qx[quse]]=0;// 将该皇后的列标记为1
			}
			if(quse==n) // n个皇后放完，增加一种方法，再回朔到上一个皇后的位置，同上
			{
				t++;				
				qx[quse]=-1;
				quse--;
				ql[n-1+quse-qx[quse]]=0;
				qr[qy[quse]+qx[quse]]=0;
				line[qx[quse]]=0;
			}
          }
	if(n%2==1)//如果皇后是奇数，下面计算在第一行的中间放皇后一共有多少种方法tt
	{
		tt=0;
		while(quse>=0 && qx[0]==n/2)
		{
						key=1;
			if(qx[quse]<n-1)
			{
					for(i=qx[quse]+1;i<n;i++)
				{
					if(line[i]==0)
					   if(ql[n-1+quse-i]==0)
						  if(qr[quse+i]==0)
						  {
						      qx[quse]=i;
						      qy[quse]=quse;
						      ql[n-1+quse-i]=1;
						      qr[quse+i]=1;
						      line[i]=1;
						      quse++;
					          key=0;
						      break;
						  }
				}
			}
			if(key)
			{
				qx[quse]=-1;
				quse--;
				ql[n-1+qy[quse]-qx[quse]]=0;
				qr[qy[quse]+qx[quse]]=0;
				line[qx[quse]]=0;
			}
			if(quse==n)
			{
				tt++;
				qx[quse]=-1;
				quse--;
				ql[n-1+qy[quse]-qx[quse]]=0;
				qr[qy[quse]+qx[quse]]=0;
				line[qx[quse]]=0;
			}
          }
	}
	end_time=clock();
	cout<<n<<"皇后问题共有 "<<2*t+tt<<" 个解!"<<endl;
	cout<<"共用时间:"<<end_time-start_time<<" 毫秒"<<endl;	
	delete []qx;
	delete []qy;
	delete []ql;   
	delete []qr;
	delete []line;	
   cout<<"还要继续么？(y/n)"<<endl;
   cin>>k;
   }while(k=='y');
}