010.cpp

包含两个文件

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

void main()
{
	clock_t start_clock, end_clock;
	int i,k,n,total,l,h,l1;
	int *a;

    printf("请输入皇后数:");
	scanf("%d",&n);
	l=n%2;      //判断皇后数为奇数还是偶数。
	h=1;        //设置皇后数为奇数时是第一次判断
	l1=n/2-1;   //计算皇后数的一半。
	if(n<4)
	{
		printf("皇后数目小于等于3的无法摆放。\n");
		return;
	}

	start_clock=clock();	
	total=0;
	a = new int[n];

	for (i=0;i<n;i++)  a[i] = 0;           //n皇后全放在第0列

	for (i=1;;)     //首先安放第0行皇后
	{  
		if(a[i]<n)    //皇后还可调整
		{
			
			for(k=i-1;k>=0;k--)  //检查与第k个皇后是否互相攻击
			{
				if(a[k]==a[i])break;
				if(k-i==a[k]-a[i])break;
				if(k-i==a[i]-a[k])break;
			}

			if (k>=0)    //与第k个皇后互相攻击
			{                           
				a[i]++;                          //第i个皇后右移一列，重测
				continue;
			}
			i++; 
			
			if(i<n) continue;                  //无冲突，安置下一行皇后
			total++;                               //方案数加1
			a[n-1]++;                           // 将第n-1个皇后右移一列，前n-1个不动
			i=n-1;                         //此处是制造机会，如不成功则回溯，关键一步

			if(a[0]>l1)                     //进行折半优化
			{
				if(l==0)                    //偶数时处理
				{
					total=2*(total-1);
					cout<<"总数:"<<total<<endl;
					end_clock=clock();
					printf("用时:%d毫秒。\n",end_clock-start_clock);
					return;
				}
				else
				{
					if(h==0)
					{
						cout<<"总数:"<<total<<endl;      //奇数时处理
						end_clock=clock();
						printf("用时:%d毫秒。\n",end_clock-start_clock);
						return;					       
					}
					total=2*(total-1);
					h=0;
					l1++;
				}
			}

		}
		else                                     //当前行皇后无法安置，回溯
		{
		
			a[i]=0;                            //当前行皇后回归0列
			i--;                                   //回溯到前一行皇后
			a[i]++;             //前一行皇后右移一列

		}
	}
}