005.cpp

包含两个文件

#include <iostream>
#include <ctime>

using namespace std;

void queen(const int &num);		//核心算法

void main(){
	while(true){//菜单
		int num;
		cout << "请输入皇后数目N = ";
		cin >> num;
		queen(num);
		cout << "\n再想算吗？(y or n)";
		char yorn;
		cin >> yorn;
		if(yorn != 'y' && yorn != 'Y'){
			cout << "结束!" <<endl;
			break;
		}
	}
	
}

void queen(const int &num){
	if(num==1){	//1皇后特殊处理
		cout <<"个数为: "<<1 <<endl;
	}else{	//非1皇后处理方法：
		const int add = num-1;
		//	动态分配空间
		int *node = new int[num];	//记录每一个皇后所在的列	
		int *col = new int[num];	//记录以被占用的列
		int *nt = new int[2*num-1];		//记录已被占用的主对角线
		int *pt = new int[2*num-1];		//记录已被占用的副对角线
		int count=0;	//统计结果的个数
		int count_mid=0;	//当num为奇数时，记录最中间的一列所得的结果
		//初始化数据
		for(int i=0;i<num;i++){
			node[i]=-1;
			col[i]=0;
		}

		for(i=0;i<2*num-1;i++){
			nt[i]=0;
			pt[i]=0;
		}
		
		int finish;	//记录停止列
		bool flag;	//奇偶的标记
		if(num%2==0){	//奇偶处理
			finish = num/2;
			flag=true;
		}else{
			finish = num/2+1;
			flag=false;
		}

		i=0;
		clock_t start_time,end_time;
		start_time = clock();
		while(i<num){
			while(true){
				node[i]++;	//列前进
				if(node[i]>=num || node[0]==finish){	//当列数超过num时处理方法
					if(i==0){	//当行数为第一行时，输出结果
						cout <<"个数为: "<<count*2-count_mid <<endl;
						cout << "结束" <<endl;
						goto end;
					}else{	//当行数不为第一行时，回溯
						node[i]=-1;
						i--;
						col[node[i]]=0;
						pt[i+node[i]]=0;
						nt[i-node[i]+add]=0;
						break;
					}
				}

				if(col[node[i]]==0 && pt[i+node[i]]==0 && nt[i-node[i]+add]==0){	//冲突条件判断
					if(i==num-1){	//当行数为最后一行时
						/*	输出每一次的结果
						for(int j=0;j<num;j++){
							cout << node[j]+1 <<" ";						
						}
						*/
						count++;
						if(flag==false && node[0]==finish-1){
							count_mid++;
						}
						//cout <<endl;
						//回溯
						col[node[i]]=0;
						pt[i+node[i]]=0;
						nt[i-node[i]+add]=0;
						node[i]=-1;					
						i--;	
						col[node[i]]=0;
						pt[i+node[i]]=0;
						nt[i-node[i]+add]=0;
						break;
					}	//否则，记录当前皇后的数据，进入下一行
					col[node[i]]=1;
					pt[i+node[i]]=1;
					nt[i-node[i]+add]=1;
					i++;
					break;
				}
			}
		}
	end:
		end_time = clock();
		cout << "所用时间：" <<end_time - start_time <<"毫秒" <<endl;
	}
}