006.cpp

包含两个文件

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

//程序生成一个动态二维数组作为棋盘.
//实现时采用加标签的方法:当在一个位置放入一个皇后后,将再放入皇后会与此位置产生攻击的地方
//加上标签,即给这些位置加上1.
//当为一个皇后找位置时,从第一列往后找,如一位置为0,则改位置放入皇后后不会与已放入的皇后攻击.
//如这列全不为0,则此路径无解,反回,撤消放入前一个皇后时所加的1,并从该位置往后找0位置.

void main()
{
	cout<<"本程序功能是求解皇后问题"<<endl;
	cout<<"   2005级     徐立钧      "<<endl;
	cout<<"\n-------------------------------------\n"<<endl;

    unsigned int number;//解的数目
	int n;//皇后数
    char hh;

    int i,j,m,k;
	int *wei;//指向一个用于回溯的数组	
	int **p;//指向动态二维数组
    clock_t start, end;

	do{

	cout<<"请输入皇后个数:"<<endl;
	cin>>n;


    //-------------------初始化-----------------
    number=0;
    wei=new int[n+1];

	p=new int* [n+1];

	for(i=1;i<=n;i++)
	{
		p[i]=new int[n+1];
	}

	for(i=1; i<=n; i++)
		for(j=0;j<=n;j++)
			p[i][j]=0;


   //---------------求解------------------------
	
	cout<<"开始求解..."<<endl;
	start=clock();

	for (j=1; j<=n/2; j++)
	{
        i=1;
		wei[i]=j;
       
	   //放置此位置后,给后面会产生冲突的位置加上标签
       for (k=0; k<n-i; k++)  p[n-k][j]++;
	   for (k=1; k<=j-1; k++)  p[i+k][j-k]++;
	   for (k=1; k<=n-j; k++)  p[i+k][j+k]++;
  
        ++i;
		k=1;

        while( i>1 )	
		{
	        while ((k <= n) && (p[i][k] != 0)) k++;				
		    if (k <= n)
			{
			     wei[i] = j = k;
		         //放置此位置后,给后面会产生冲突的位置加上标签
                for (k=0; k<n-i; k++)  p[n-k][j]++;
				m=j-1<n-i? j-1:n-i;
	            for (k=1; k<=m; k++)  p[i+k][j-k]++;
                m=n-j<n-i? n-j:n-i;
	            for (k=1; k<=m; k++)  p[i+k][j+k]++;
                 k=1;
			     ++i;
			}
			
		    else
			{   //找不到能放的位置
                i--;//后退
			   
                 j = wei[i];
	             //撤除所加标签
				 for (k=0; k<n-i; k++)  p[n-k][j]--;
                 m=j-1<n-i? j-1:n-i;
	             for (k=1; k<=m; k++)  p[i+k][j-k]--;
                 m=n-j<n-i? n-j:n-i;
	             for (k=1; k<=m; k++)  p[i+k][j+k]--;
			     k=wei[i]+1;
			}
		    if (i > n) 
			{   //是一个解
			    number++;
			    i -=2;//退回
				j = wei[i];
                //撤除所加标签
	            for (k=0; k<n-i; k++)  p[n-k][j]--;
                m=j-1<n-i? j-1:n-i;
	            for (k=1; k<=m; k++)  p[i+k][j-k]--;
                m=n-j<n-i? n-j:n-i;
	            for (k=1; k<=m; k++)  p[i+k][j+k]--;
		    	k=wei[i]+1;
			}
		}
	}

   number*=2;

    //若为奇数的处理
	if(n%2)
	{
        i=1;
		wei[i]=j=n/2+1;
       //放置此位置后,给会产生冲突的位置加上标签
       for (k=0; k<n-i; k++)  p[n-k][j]++;
       m=j-1<n-i? j-1:n-i;
	   for (k=1; k<=m; k++)  p[i+k][j-k]++;
       m=n-j<n-i? n-j:n-i;
	   for (k=1; k<=m; k++)  p[i+k][j+k]++;
  
        ++i;
		k=1;
        while(i > 1)
		{
	        while ((k <= n) && (p[i][k] != 0)) k++;		
		    if (k <= n)
			{
			     wei[i] = j = k;
		        //放置此位置后,给会产生冲突的位置加上标签
                for (k=0; k<n-i; k++)  p[n-k][j]++;
                m=j-1<n-i? j-1:n-i;
	            for (k=1; k<=m; k++)  p[i+k][j-k]++;
                m=n-j<n-i? n-j:n-i;
	            for (k=1; k<=m; k++)  p[i+k][j+k]++;
                 k=1;
			     ++i;
			}
		    else
			{   //找不到能放的位置
                i--;
			   //撤除所加标签
				j=wei[i];
	            for (k=0; k<n-i; k++)  p[n-k][j]--;
                m=j-1<n-i? j-1:n-i;
	            for (k=1; k<=m; k++)  p[i+k][j-k]--;
                m=n-j<n-i? n-j:n-i;
	            for (k=1; k<=m; k++)  p[i+k][j+k]--;
			    k=wei[i]+1;
			}
		    if (i > n) 
			{
			    number++;
			    i -=2;
				j=wei[i];
                //撤除所加标签
	            for (k=0; k<n-i; k++)  p[n-k][j]--;
                m=j-1<n-i? j-1:n-i;
            	for (k=1; k<=m; k++)  p[i+k][j-k]--;
                m=n-j<n-i? n-j:n-i;
	            for (k=1; k<=m; k++)  p[i+k][j+k]--;
		    	k=wei[i]+1;
			}
		}
	}

	end=clock();

    cout<<"OK!  求解完毕! "<<endl;
	cout<<" "<<n<<" 皇后共找到 "<<number<<" 个解"<<endl;
    cout<<"共用时 "<<end-start<<" 豪秒"<<endl;

    delete []p;
    delete []wei;
	p=NULL;
	wei=NULL;

	cout<<"\n是否继续?(y/n):"<<endl;
	cin>>hh;

	}while(hh=='y');


	char cc;
	cout<<"请击一键退出"<<endl;
	cin>>cc;

}