015.cpp

包含两个文件

#include<iostream>
#include<ctime>
using namespace std;

struct queen
{
  char x;
  char lable;
  char times;
  bool used;//标志该点是否已使用
};

int judge(char x,char y,queen sub_place[]);

void main(void)
{
char n=12;//8皇后
char i=0;
char j=0;
char k;
int num=0;
int odd_num=0;
int temp=0;
queen *queen_eight;
queen *queen_p;
char line_num=0;

  cout<<"请输入n=\n";
  cin>>num;
  n=num;
  num=0;
  clock_t start_time,end_time;
  start_time=clock();cout<<"开始时间:"<<start_time<<"毫秒"<<endl;      //开始计时
  queen_eight=new queen[n];
  queen_p=queen_eight;

  for(k=0;k<n;k++)
  {
     queen_eight[k].x=-1;//65536
	 queen_eight[k].lable=0;
	 queen_eight[k].times=0;
  }
  queen_eight[0].x=0;
  line_num=1;
  while(1)
  {     
	  while(1)
	  {
		 for(j=queen_eight[line_num].lable;j<n;j++)
		 {
		   if(judge(line_num,j,queen_eight)==1)//等于1不冲突
		   {
			  queen_eight[line_num].x=j;
			  queen_eight[line_num].lable=j+1;
			  queen_eight[line_num].times=j;
			  break;
		   }		 
		 }		   
		 if(queen_eight[line_num].x>-1||j==n)
		{
			 queen_eight[line_num].times=j-1;
			 break;
		}
	 }
     if(queen_eight[line_num].x==-1)
	 {
		 while(queen_eight[line_num].times==n-1)
		 {
			if(line_num>0)
			{			   
			   queen_eight[line_num].lable=0;//
			   queen_eight[line_num].times=0;
			   queen_eight[line_num].x=-1;
			   line_num--;
			   queen_eight[line_num].x=-1;
			  if(line_num==0)
			   {
                  queen_eight[0].x=++i;
				  line_num=1;
			   }
			}
		 }
	 }
	 else
	 {
		 if(line_num<n-1)
		 {
		    line_num++;
		 }
		 else
		 {
             queen_eight[line_num].lable=n-1;
			 queen_eight[line_num].times=n-1;
		 }
	 }
	 if(queen_eight[n-1].x>-1)
	 {
		 num++;

         while(queen_eight[line_num].times==n-1)
		 {
			if(line_num>0)
			{			   
			   queen_eight[line_num].lable=0;//
			   queen_eight[line_num].times=0;
			   queen_eight[line_num].x=-1;
			   line_num--;
			   queen_eight[line_num].x=-1;
			   if(line_num==0)
			   {
                  queen_eight[0].x=++i;
				  line_num=1;
			   }
			}
		 }
	 }
	if((i==n/2)&&(j==n)&&(n%2==0))//n为偶数且当i==n/2时跳出循环
	{   
		num*=2;
		break;
	}
	if((n%2==1)&&(i==n/2))
	{
		if(num!=temp)
		{
		  odd_num++;
		  temp=num;
		}
	}
	if((i==n/2+1)&&(j==n)&&(n%2==1))//n为奇数且当i==n/2时跳出循环
	{
	    num=2*num-(odd_num-1);
		break;
		}
  }
  cout<<int(n)<<"皇后问题共有"<<num<<"个解\n";
  end_time=clock();cout<<"OK!计算已完成,运行时间为"<<end_time-start_time<<"毫秒"<<endl;
}
int judge(char y,char x,queen sub_place[])
{

  char k=0;
  for(k=y-1;k>=0;k--)
  {
     if((x-sub_place[k].x==y-k)||(sub_place[k].x-x==y-k))
	 {
	    return 0;
	 }
	 if(x==sub_place[k].x)
	 {
		return 0;
	 }
  }
  if(y<1)
  {
	  return 0;
  }
return 1;
}