[人工智能实践]爬山法，分支界限法求解皇后问题「建议收藏」

皇后问题通常方法是回溯，但效率较低。

另外一种方法是使用随机算法，利用分支界限法的思想作为启发函数。10000以内规模的问题效率不错。

具体方法如下：

用一维数组存储每一行所放皇后所在的列数，要保证所有皇后所在列均不同，只需要保证数组中无相同的值即可，也就是数组的值为一个n的全排列。因为随着n规模的增大，计算量增大的同时解的数目也增多，所以本算法采用随机生成的全排列来进行尝试。

ru和rd数组纪录每条正，负对角线上皇后的数目。可对正负对角线分别编号，可利用棋子的行列位置O(1)时间范围内求得其所在的对角线号。便于统计每条对角线上棋子的数目。

因每条对角线上的皇后数目不能多于一个，这是我们的目标状态。可取启发函数h为当前状态各条对角线上多余皇后之和。

搜索方向需满足使得h值更小的状态。

若当前排列无解，则重新生成全排列。

实现：

//爬山法解决皇后问题
#include<string.h> 
#include<stdlib.h> 
#include<time.h> 
#include<iostream> 
using namespace std;
const int size=1000000; 
int board[size],ru[size*2],rd[size*2],n;

int f(){//统计对角线需要调整的皇后数
	int i,r=0; 
	memset(ru,0,sizeof(ru)); 
	memset(rd,0,sizeof(rd)); 
	for(i=0;i<n;i++){ 
		ru[board[i]-i+n-1]++; //负对角线
		rd[board[i]+i]++; //正对角线
	} 
	for(i=0;i<2*n-1;i++){ 
		if(ru[i]>1) r+=ru[i]-1; 
		if(rd[i]>1) r+=rd[i]-1; 
	} 
	return r;
} 

void randgen(){ // 随即生成全排列
	for(int i=0;i<n;++i)
		board[i]=i;
	for(int i=0;i<n;++i){
		int pos=rand()%n;
		swap(board[i],board[pos]);
	}
} 

int main(){ 
	srand((unsigned)time(NULL)); 
	int i,j,temp,now,t1,t2,fnow; 
	while(cin>>n){
		if(n==2 || n==3){
			cout<<"No answer"<<endl;
			continue;
		}
		while(1){ 
			randgen(); 
			now=f(); 
		label:
			if(now==0) 
				break;
			//尝试通过交换减少需要调整皇后数
			for(i=0;i<n-1;i++){ 
				for(j=i+1;j<n;j++){ 
					int fnow=now;
					--ru[board[i]-i+n-1];
					if(ru[board[i]-i+n-1])
						--fnow;
					--rd[board[i]+i];
					if(rd[board[i]+i])
						--fnow;
					++ru[board[i]-j+n-1];
					if(ru[board[i]-j+n-1]>1)
						++fnow;
					++rd[board[i]+j];
					if(rd[board[i]+j]>1)
						++fnow;
					--ru[board[j]-j+n-1];
					if(ru[board[j]-j+n-1])
						--fnow;
					--rd[board[j]+j];
					if(rd[board[j]+j])
						--fnow;
					++ru[board[j]-i+n-1];
					if(ru[board[j]-i+n-1]>1)
						++fnow;
					++rd[board[j]+i];
					if(rd[board[j]+i]>1)
						++fnow;
					swap(board[i],board[j]);
					if(fnow<now){
						now=fnow;
						goto label;
					}
					swap(board[i],board[j]);
					--rd[board[j]+i];
					--ru[board[j]-i+n-1];
					++rd[board[j]+j];
					++ru[board[j]-j+n-1];
					--rd[board[i]+j];
					--ru[board[i]-j+n-1];
					++rd[board[i]+i];
					++ru[board[i]-i+n-1];
				} 
			} 
		} 
		cout<<"("<<board[0]+1;
		for(int i=1;i<n;++i){
			cout<<","<<board[i]+1;
		}
		cout<<")"<<endl;
	}
	return 0; 
}