K皇后问题递归解法

 1 #include<iostream>
 2 #include<cmath>
 3 #include<ctime>
 4 using namespace std;
 5 
 6 bool check(int row,int *a)
 7 {
 8     for(int i=0;i<row;i++)
 9         if (a[i]==a[row] || fabs(a[i]-a[row])==fabs(i-row))
10             return false;
11     return true;
12 }
13 
14 void show(int *a,int num,int k)
15 {
16     cout<<"the "<<num<<" answer is:"<<endl;
17     cout<<"-------------------"<<endl;
18     for(int i=0;i<k;i++)
19         for(int j=0;j<k;j++)
20         {
21             if (a[i]==j)
22                 cout<<'*';
23             else cout<<'o';
24             if ((j+1)%k==0)
25                 cout<<endl;
26         }
27 }
28 void findpos(int row,int *a,int &num,int k)
29 {
30     if(row==k)
31     {
32         num+=1;
33         show(a,num,k);
34     }
35     else{
36         for(int i=0;i<k;i++)
37         {
38             a[row]=i;
39             if(check(row,a))
40                 findpos(row+1,a,num,k);
41         }
42     }
43 }
44 int main(void)
45 {
46     int k;
47     cout<<"the number of que is:";
48     cin>>k;
49     int *a=new int[k];//记录每行皇后对应的列
50     int num=0;//记录解的数量
51 
52     clock_t start,end;
53     start=clock();
54 
55     findpos(0,a,num,k);
56     delete [] a;
57 
58     end=clock();
59     double totaltime=double((end-start))/CLOCKS_PER_SEC;//clock_t相当于long型
60     cout<<"time elapses "<<totaltime<<" seconds";
61     system("pause");
62     return 0;
63 }
64 　　
65 
66 View Code

View Code

利用位运算来计算K皇后问题解的个数，有些限制，是Matrix67提到的方法，bitmap的思想，速度快，内存小

#include<iostream>
#include<ctime>
using namespace std;
void Queen(int column,int ld,int rd,int k, int &num)
{
	//column,ld,rd中1表示禁位
	int upperlim=(1<<k)-1;//01111
	int pos,p;
	if(column!=upperlim)//列还有空位
	{
		pos=upperlim & ~(column|ld|rd);//ld,rd? 取反后1表示可以放的位置
		while(pos !=0)
		{
			p=pos & -pos;//01001->00001 取出最右面的一个1
			pos-=p;

			Queen(column+p,(ld+p)<<1,(rd+p)>>1,k,num);//每向下移一行，对角线的禁位要要偏移一个单位
		}
	    //取完所有可放的位置
	}
	else num+=1;// 当列放满时，一次大循环结束

}
void ToTwo(int n)
{
	for(int i=0;i<32;i++,n<<=1) cout<<(n<0);
}
int split(int n,int k)
{
	return n & ((1<<k)-1);
}

int main(void)
{
	clock_t start,end;
	int k,num=0;
	cout<<"皇后的数量：";//因为是用利用位代替了数组的传递，还有一位要用来移位时溢出
	                     //这里int型决定了最大31个皇后
	cin>>k;
	start=clock();
    Queen(0,0,0,k,num);
	cout<<num<<endl;
	end=clock();
	double totaltime=double(end-start)/CLOCKS_PER_SEC;
	cout<<"time elapse: "<<totaltime<<" seconds"<<endl;
	return 0;
}
//16个皇后，14772512，40s