002bjs.cpp

来自「包含两个文件」· C++ 代码 · 共 107 行

//N=16,运行155秒,N=17 运行1109秒.

#include <iostream.h>
#include <assert.h>
#include <time.h>
void main()
{
 	clock_t ts,te;
	 int n,sum=0;
 	int i,j,p,q,k,l,m,x;
 	bool flag;
 	char ch;
 	register int **chess, *site;
 	do
 	{
	                cout<<"输入皇后个数:";
  		cin>>n;
  		sum=0;
  		if(n==1) {cout<<"有1个解!"; return;}
  		else  if(n<=0) {cout<<"无解!";return;}
  	                chess=new int*[n+1];
   		assert(chess!=0);
      		for(i=1;i<=n;i++)
   		{
		    chess[i]=new int[n+1]; //申请一个N*N的棋盘
 		    assert(chess[i]!=0);
  		    for(j=1;j<=n;j++)chess[i][j]=0;
   	}
 	site=new int[n+1];
   	assert(site!=0);     //site[n]存放各行皇后位置
   	for(i=1;i<=n;i++)site[i]=0;
   	ts=clock();
   	i=1;
   l0:
   	if(i<=n)
   	{
    	     j=1;
   l1:
   	 if(j<=n)
	{
     		if(chess[i][j]==0)
	 	{
   	  	    site[i]=j;   //找到一个不发生冲宊位置
      		    p=j-1;
	  	    q=j+1;
                                     for(k=i+1;k<=n;k++)       //在棋盘上该位置上方标示该位置控制泛围
	                    {
	   		if(p) chess[k][p--]++;
	   		chess[k][j]++;
	   		if(q<=n) chess[k][q++]++;
	  	     }  
	  	     i++;              //找下一行
	  	    goto l0;
	                }
                                else
	               {
      		     j++;            //若当前位置冲宊,判断该行下一列
      		    goto l1;
	                }
	}
               else
               {
     	    i--;          //若当前行无位置,回朔,抹去下一行位置控制泛围
                    for(p=1;p<=i;p++)        //折半判断,是否退出
	   {
	        x=n+1-site[p];
                        if(x>site[p]) goto l2;
	        else 
	        if(x<site[p]) goto end;
	   }
 l2:
                    j=site[i];             //回朔,从棋盘上抹去下一行位置控制泛围
                    p=j-1;
                    q=j+1;
                    for(k=i+1;k<=n;k++)
	   {
	        if(p) chess[k][p--]--;
	        chess[k][j]--;
                        if(q<=n) chess[k][q++]--;
	    }
                    j++;             
                   goto l1;       //判断行下一行下一列
	}
            }
            else
           {                                //若找到一个位置,记数,/回朔
	for(p=1;p<n;p++)                //折半判断,是否退出
               {
	     x=n+1-site[p];
                     if(x>site[p]) break;
	     else 
	     if(x<site[p]) goto end;
	}
               sum+=2;              //记数器加2
               i=n-1;              //回朔
    goto l2;
   }
end:
   te=clock();
   cout<<"\n共有"<<sum<<"种解法!\n";
   cout<<"  共记用时:"<<te-ts<<"毫秒!\n";
   cout<<"继续(y?):";
   cin>>ch;
 }
 while(ch=='y'||ch=='Y');
}