014.cpp

包含两个文件

/* 
算法思想：用一个n个int形的数组来作为棋盘的X坐标，同时这个数组本身的位置就代表Y坐标。
用一个布尔形的数据来判断这个点是否会跟其他点参生冲突。这样逐行的寻找可以放置的坐标，直到N-1行
如果能找到N-1行的不冲突点，则就找到了一个结果。 如果N为偶数，则在寻找过程中，只需要寻找第一行X
坐标0至n/2的结果就可以了，因为他们是对称的，所以只要将0至n/2的结果乘2就可以得出总共的结果。
如果N是奇数，则寻找第一行X坐标0至n/2的结果乘2，然后还要加上n/2+1的结果，就可以求出总共的结果。
*/
#include <iostream.h>
#include <time.h>
typedef struct 
{ 
bool use;
int x;
} QueenN;
void initQueenN(QueenN *p, int n);
void main()
{
clock_t start_time,end_time;
int n, result = 0, YOld, y, k, odd = 0, JudgeN = 0, answer = 0, judge = 0, JudgeO = 0; 
QueenN *p;
cout<<"请输入N皇后问题的N:"<<endl;
cin>>n;
cout<<"\n";
JudgeN = n / 2;
odd = n % 2;//判断N是奇数还是偶数
p = new QueenN [n];
start_time=clock();
initQueenN(p,n);// 初始化n
while (p[0].x<JudgeN) 
{
	for (k=1; k<n; k++) //将第二行以上的数据都清零
	{
		p[k].x = 0;
		p[k].use = false;
	} 
	y = 1;
	while (p[1].x < n)//对第二行以上进行循环
	{
		YOld = y - 1;
		while ((p[y].x<n)&&(YOld>=0)) // 对具体一行进行循环
		{
			if ((p[y].x != p[YOld].x)&&(p[y].x != (p[YOld].x + (y - YOld)))&&(p[y].x != (p[YOld].x - (y - YOld)))) //判断具体一行的具体位置对于其下的所有行位置是否可用
			{
			p[y].use = true;
			}
			else 
			{
				p[y].use = false; 
				p[y].x++;
				YOld = y - 1;
			}
		if (p[y].use == true) YOld--;
		}
		if ((p[n-1].use == true)&&(YOld == -1)) // 最高行找到一个可放位置
		{
			result++;
			p[n-1].use = false;
		}
				
		if (YOld == -1) // 某行找到一个可用位置
		{
			y++;
			if (y==n)  
			{
				y--;
				p[y].x++;
			}
			else
				p[y].x = 0;
			
		}	
		if ((p[y].x == n) && (p[1].x != n)) //高于第二行的某行找完
		{
			p[y].x = 0;
			y--;
			p[y].x++;
		}
						
	}
	p[0].x++;
}
result = result * 2; //实现翻倍
answer = answer + result;
result = 0;
if (odd > 0)  // 是奇数则在查找一次结果
{
	for (k=1; k<n; k++) 
	{
		p[k].x = 0;
		p[k].use = false;
	}
	y = 1;
	while (p[1].x < n)
	{
		YOld = y - 1;
		while ((p[y].x<n)&&(YOld>=0))
		{
			if ((p[y].x != p[YOld].x)&&(p[y].x != (p[YOld].x + (y - YOld)))&&(p[y].x != (p[YOld].x - (y - YOld))))
			{
			p[y].use = true;
			}
			else 
			{
				p[y].use = false; 
				p[y].x++;
				YOld = y - 1;
			}
		if (p[y].use == true) YOld--;
		}
		if ((p[n-1].use == true)&&(YOld == -1)) 
		{
			result++;
			p[n-1].use = false;
		}
				
		if (YOld == -1)
		{
			y++;
			if (y==n)  
			{
				y--;
				p[y].x++;
			}
			else
				p[y].x = 0;
			
		}	
		if ((p[y].x == n) && (p[1].x != n))
		{
			p[y].x = 0;
			y--;
			p[y].x++;
		}
						
	}

}
answer = answer + result;

end_time=clock();
cout<<"生成"<<n<<"皇后共用"<<end_time-start_time<<"毫秒"<<endl;
cout<<n<<"皇后共有结果"<<answer<<"个解."<<endl;
}

void initQueenN(QueenN *p, int n)
{
int i;
for (i=0; i<n; i++) 
{
	p[i].use = false;
	p[i].x = 0;
}
}