009.cpp

包含两个文件

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

#include <iostream>
using namespace std;

/*判别函数，判断是否能继续向前一步走，如果返回值为1，前进一步，返回值为0，后退一步*/
int judge(int i,int j,int *place);

int main()
{
	clock_t start_time,end_time;          //时间变量
	int queen_number,i=0,j=0,tt=0,tt1=0,k;      //queen_number为N皇后的N值
	cout<<"本程序求解N皇后问题解的个数。"<<endl;
	cout<<"请输入您所要求解的N值:";cin>>queen_number;cout<<endl;
	int *place = new int[queen_number];            //动态分配一个一维数组
	for(k=0;k<queen_number;k++)  place[k]=0;       //赋初值，place[i]皇后占据了第i行的第place[i]列
	start_time=clock();cout<<"计算开始时间为："<<start_time<<endl;
	if(queen_number%2==0)
    {while(j<queen_number)
	{
		if(j<queen_number-1) //第j列不在最右一列
		{if(judge(i,j,place)==1)
		         {
                  if(i==queen_number-1)   //达到最高一行且判别合格，解的总数累加1 
				  {
					  tt++;--i;               
					  while(i>0 && place[i]==queen_number-1) --i;
					  if(i==0 && place[i]==queen_number/2-1) break;
					  j=++place[i];continue;			  
				  }  
		          j=0;place[++i]=j;       //判别合格，往前一行，从0列开始继续检验
		         }
	     else
		         {
		          place[i]=++j;     //判别不合格，行不变，向右推一列，继续检验
		         }
		}
        if(j==queen_number-1)         //第j列真好在最右一列
		{if(judge(i,j,place)==1)
		         {
		          if(i==queen_number-1)   //达到最高行且判别合格，向后退然后右推一列继续检验
				  {
					  tt++;
					  while(i>0 && place[i]==queen_number-1) --i;
					  if(i==0 && place[i]==queen_number/2-1) break;
					  j=++place[i];
				  }
				  else {j=0;place[++i]=j;} //判别合格，往前一行，从0列开始继续检验
		         }
	     else
		         {  //无路可走了，向后退然后右推一列继续检验
                  while(i>0 && place[i]==queen_number-1) --i;
				  if(i==0 && place[i]==queen_number/2-1) break;
				  j=++place[i];
		         } 
		}
	}
	end_time=clock();cout<<"计算结束时间为："<<end_time<<endl;
	cout<<"程序运行共耗时为："<<end_time-start_time<<endl;
	cout<<queen_number<<"皇后问题的解的个数为："<<tt*2<<endl;
	}
	if(queen_number%2!=0)
    {tt=0;while(j<queen_number)
	{
		if(j<queen_number-1) //第j列不在最右一列
		{if(judge(i,j,place)==1)
		         {
                  if(i==queen_number-1)   //达到最高一行且判别合格，解的总数累加1 
				  {
					  if(place[0]<queen_number/2) tt++;
                      if(place[0]==queen_number/2) tt1++;
					  --i;               
					  while(i>0 && place[i]==queen_number-1) --i;
					  if(i==0 && place[i]==queen_number/2) break;
					  j=++place[i];continue;			  
				  }  
		          j=0;place[++i]=j;       //判别合格，往前一行，从0列开始继续检验
		         }
	     else
		         {
		          place[i]=++j;     //判别不合格，行不变，向右推一列，继续检验
		         }
		}
        if(j==queen_number-1)         //第j列真好在最右一列
		{if(judge(i,j,place)==1)
		         {
		          if(i==queen_number-1)   //达到最高行且判别合格，向后退然后右推一列继续检验
				  {
					  if(place[0]<queen_number/2) tt++;
                      if(place[0]==queen_number/2) tt1++;
					  while(i>0 && place[i]==queen_number-1) --i;
                      if(i==0 && place[i]==queen_number/2) break;
					  j=++place[i];
				  }
				  else {j=0;place[++i]=j;} //判别合格，往前一行，从0列开始继续检验
		         }
	     else
		         {  //无路可走了，向后退然后右推一列继续检验
                  while(i>0 && place[i]==queen_number-1) --i;
				  if(i==0 && place[i]==queen_number/2) break;
				  j=++place[i];
		         } 
		}
	}
	end_time=clock();cout<<"计算结束时间为："<<end_time<<endl;
	cout<<"程序运行共耗时为："<<end_time-start_time<<endl;
	cout<<queen_number<<"皇后问题的解的个数为："<<tt*2+tt1<<endl;
	}
	delete []place;
    return 0;
}

int judge(int i,int j,int *place) //判别函数，判断能不能继续向前走一行
{
    for(int k=i-1;k>=0;k--)
    {
        if(j==place[k] || i-k==j-place[k] || i-k==place[k]-j)
        return 0;
    }
    return 1;
}