003zcy.cpp

包含两个文件

#include <iostream>
#include <time.h>
using namespace std;
typedef  unsigned long*    plong;
int main()
{
	cout<<"2005 ZCY 皇后个数16-120494："<<endl;
    cout<<"2005 ZCY 皇后个数17-有95815104个解  876811毫秒"<<endl;
    cout<<"2005 ZCY 皇后个数18-有666090624个解 6544059毫秒"<<endl;

	register unsigned long r,l ,m;
    int i, jilu_p=0,n,n1;
	unsigned long sum=0;
	int k,y;
    
next:	cout<<"输入皇后个数："<<endl;
	
			
	int n_hh;
	cin>>n_hh;n=n_hh-1;n1=n_hh>>1;
	sum=0;jilu_p=0;
	int  *jilu=new int[n_hh];
	for( i=0;i<n_hh;i++)jilu[i]=0;
	long flag1,flag=0x80000000;
	flag>>=31-n_hh;
	flag1=~flag;
	plong *pp=new plong[n_hh];
	plong p,q;
	for( k=0;k<n_hh;k++)
	{
		p=new unsigned long[n_hh];
	    for( i=0;i<n_hh;i++)
		{
		  p[i]=0;
		}
    	pp[k]=p;
	}

	unsigned long sum_1=0;
	unsigned long t=clock();
	y=n/2+1;//利用解的对称性
	while(jilu_p>0 || jilu_p==0 && jilu[0]<y)
	{
		for(k=jilu[jilu_p],m= 1<<k;k<n_hh;k++,m<<=1)
		{	
			q=pp[jilu_p];
			if(q[jilu_p]&m)continue;
			jilu[jilu_p]=k;
			if(jilu_p<n)
			{
				p=pp[++jilu_p];
				r=l=m;
            	for(i=jilu_p;i<n_hh;i++)
				{
					r>>=1;l<<=1;
	                if(~((p[i]=q[i]|r|l|m)|flag)==0){jilu_p--;break;}

				}
                if(i==n_hh)k=n_hh;
			}
			else
			{
				sum++;k=n;
			}

		}
		if(k==n_hh)
		{
			jilu[jilu_p]=0;jilu_p--;jilu[jilu_p]++;}
			if(jilu_p==0 && jilu[0]==n1)sum_1=sum;
		}
		cout<<"共有"<<sum+sum_1<<"个解"<<endl;cout<<sum<<endl;
		cout<<"共用时"<<clock()-t<<"毫秒"<<endl;

		for( i=0;i<n_hh;i++)
		{
			delete []	(pp[i]);
		}
		delete[]pp;
		if(!jilu)delete []jilu;
		cout<<"是否继续(Y/n)?"<<endl;
		char ch;
		cin>>ch;
		if(ch=='y')goto next;
		return 0;
}