007-1.cpp

包含两个文件

#include<iostream>
#include<ctime>
using namespace std;
int answer_number=0;//记录对称法解的个数
int mid_num=0;//记录当第一行的皇后在中间行时，解的个数
void queen(int &N,int *place,int *cul_flag);
void main()
{	
	int n=0;
	char ch='Y';
	while(ch=='Y'||ch=='y')
	{
		cout<<"计理所 2005 刘成德"<<endl;
		cout<<"本函数实现N皇后问题，输入任意的N将输出所有解，和解的个数"<<endl;
		cout<<"请输入N："<<endl;
		cin>>n;
		clock_t Start_time=clock();
		answer_number=0;
		mid_num=0;
		int parity=n%2;//判断n是奇数还是偶数
		int *place=new int[n];//存放某一行的皇后所在的列
		int *cul_flag=new int[n];//设置某列是否放元素的标记
		for(int i=0;i<n;i++)//初始化
		{cul_flag[i]=0;
		place[i]=0;}
		queen(n,place,cul_flag);//调用函数
		clock_t End_time=clock();
		if(parity==0)//如果是偶数，那么就是统计结果×2，因为用了对称法
		cout<<"结果是："<<answer_number*2<<"个"<<endl;
		else
			cout<<"结果:"<<answer_number*2-mid_num<<"个"<<endl;//否则是奇数，结果就是统计结果×2－当第一行的皇后在中间时的解的个数
		cout<<endl<<"一共用时间"<<End_time-Start_time<<"毫秒"<<endl;
		cout<<"是否再来一次：Y/N"<<endl;
		cin>>ch;
	}
}
void queen(register int &N,int *place,int *cul_flag)
{
	register int i=0,j=0,collision_juge=0;
	register int mid=(N-1)/2+1,mid_flag=(N-1)/2,N_1=N-1;
flag:for(;i<N;i++)//从第一行开始试放
		for(;j<N;j++)
			{
			    if(place[0]==N_1/2+1)
					return;
				if(cul_flag[j]==1) //利用标记位判断，是否冲突，这样可以提高速度，因为同一列只判断一次
					collision_juge=0;
				else
				{
					for(int k=i-1;k>=0;k--)//判断对角线上是否冲突，利用距离，即只要补组成正方形
					{
						if(i-k==place[k]-j){
							collision_juge=0;
							goto juge;}//一旦发现冲突，就立刻跳出去
						if(i-k==j-place[k]){
							collision_juge=0;
							goto juge;}
					}
					collision_juge=1;
				}
         juge:if(collision_juge==0)//有冲突
				{
					if(j==(N_1))//有冲突，并且到了最后一列了，所以现在就必须得回溯
					{
						for(int index=i-1;index>=0;index--)//回溯都是从当前行的上一行开始
							{
								if(place[index]<(N_1))//可以修改，进行回溯
								{
									if(place[0]==mid)//对称法，跳出的条件
										return;
									else
									{
										cul_flag[place[index]]=0;//设置标记位为有元素
										j=place[index]+1;//调整位置到下一列
								    	i=index;
									    goto flag;//回溯到修改的位子，进行判断
									}
								}//if
								else//这一行不能回溯，应检测上一行是否可以回溯
								{
									cul_flag[N-1]=0;//设置标记为没有放元素，并跳到上一行进行检查
									 continue;
								}//else
							}//for
						}//if
					else// 有冲突，但不是最后一列，所以，看下一列的情况
						continue;
				}//if
				else//没有冲突
				{
				  if(i==N_1)//找到一个解空间，需要处理保存解,并进行回溯
				  {
					place[i]=j;//保存i行的结果
					answer_number++;
					cul_flag[j]=0;
				    /*for(int q=0;q<N;q++)//输出结果模块
					{
					   cout<<place[q]<<",";
					   cout<<N-place[q]-1<<"  ";
					}
					cout<<endl;*/
					if(place[0]==mid_flag)//记录当第一行的皇后在中间时候的解的个数
					  ++mid_num;
					for(int index=N-2;index>=0;index--)
					{
						if(place[index]<(N_1))//可以修改，进行回溯
						{
							if(place[0]==mid)
							  return;
							else
							{
								cul_flag[place[index]]=0;
								j=place[index]+1;
								i=index;
								goto flag;//回溯到修改的位子，进行判断
							}
						}//if
						else//这一行不能回溯，应检测上一行是否可以回溯
						{
						   cul_flag[N-1]=0;
						   continue;
						}
					}//for
				}//if
				else//这一行找到了位置，需要放入，并进行下一行
				{
					place[i]=j;
					cul_flag[j]=1;
					j=0;
					break;
				}
			}//没有冲突完毕else
		}//for循环
}