008.cpp

包含两个文件

#include <stdlib.h>
#include <stdio.h>
#include<time.h> 
//  优化方向：1.两条斜线和在同一列做成标记，不用循环判断冲突
//            2.奇数和偶数各减少一个点
//
int Nqueen(int n);
bool judge(int *a, int i, int n);
void main()
{
	clock_t start_time,end_time; //时间变量
	int n,sum;
	printf("2005级唐宇，n皇后问题\n");
	printf("请输入皇后数: ");
	scanf("%d",&n);
	printf("开始查找%d皇后数，请稍等。。。\n",n);
	start_time=clock();
	sum=Nqueen(n);
	 end_time=clock();
	printf("%d皇后共有%d种摆法,耗时：%d毫秒\n",n,sum,end_time-start_time);
	getchar();
	getchar();
}

int Nqueen(int n)
{
	bool *col,*bias;
	int k=0,m=0,*a,odd,b;
	int *leftBias,colodd=0,coleven=0;
	a=(int *)malloc(n*sizeof(int));
	col=(bool *)malloc(n*sizeof(bool));
	bias=(bool *)malloc(2*n*sizeof(bool));
	leftBias=(int *)malloc(2*n*sizeof(int));
	for(k=0;k<n;k++)
	{
		col[k]=true;
		bias[k]=true;
		bias[k+n]=true;
		leftBias[k+n]=0;
		leftBias[k]=0;
	}
	if(n%2!=0)
	{
		odd=n/2;
		k=0;
	}
	else
	{
		odd=-1;
		k=1;
	}

	register int i,j;
	 for(i=0;i<n+1;i++)
		{
			if(j==n)              //退到的行已经在最后一列
			{
				b=i-2;
				col[a[b]]=true;  //把退到行的列置为有效
				bias[a[b]-b+n]=true;
				leftBias[a[b]+b]--;
				j=a[b]+1;
				i=b;
			}
			else
			{
				j=0;
			}
			for(;j<n;j++)
			{
				if(i==0)                           //如果是零行就顺次摆放
				{
					if(k>=n/2)
					{
							if(odd==-1)                    //如果皇后数是偶数
							{
								return 2*m+2*coleven;
							}
							else              //如果皇后数是奇数 
							{
								return 2*m+colodd;
							}
					}
					col[k]=false;                  //被占用的列被标记
					bias[k-i+n]=false;             //右斜线被标记
					leftBias[i+k]++;
					a[i]=k++;break;
				}
				else
				{
					if(!bias[j-i+n]||!col[j]||leftBias[i+j]>0)      //j列是否已使用和，此斜线是否被用
					{
						continue;
					}
					a[i]=j;
					if(i==n-1)                        //找到最后一个点，成功一个 
						{
							m++;					  //记录成功数

							if(odd==-1)                    //如果皇后数是偶数
							{
								if(a[n-1]==0||a[n-1]==n-1)
								{
									coleven++;
								}
							}
							else              //如果皇后数是奇数 
							{
								if(a[odd]==0||a[odd]==n-1)
								{
									colodd++;
								}
							}
							
					    	//for(b=0;b<n;b++)
						//	{
						//		printf("%d,%d\t",b,a[b]);
						//	}
						//	printf("\n");
						}
						else{
							col[j]=false;
							bias[j-i+n]=false;
							leftBias[i+j]++;
							break;
						}
					}
				}
			}

	 return 0;
}