八皇后问题

╰+哭是因爲堅強的太久メ 2022-07-14 00:17 217阅读 0赞

一、问题描述

![Center][]

在8x8的国际棋盘上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能同一行、同一列、同一斜线上。

八皇后问题可以扩展为n皇后问题，这是棋盘的大小变为nxn，皇后的个数也变成n，仅当n=1或n>=4时有解。

二、问题分析

设每个皇后的位置为（i,try\[i\]），表示放置在第i行，try\[i\]列

若n个皇后互相不攻击，即![Center 1][]

1、传统的回溯法

置当前行为第1行，当前列为第1列，即i←j←1;  
while i ≤ 8 do \{ // 当前行号i≤ 8  
检查当前行i：从当前列j起向后逐列试探，寻找安全列号；  
if 找到安全列号 then \{  
    放置皇后，将列号记入栈，并将下一行置为当前行(i++);  
    j←1; //当前列置为1  
\} else \{  
   退栈回溯到上一行，即i--；  
   移去该行已放置的皇后，以该皇后所在列的下一列作为当前列；  
\}  
\}

为了找出所有满足条件的解，定义递归函数void backtrace(int t),放置第t个皇后

bool place(int t)检验当前放置的第k个皇后是否合法

#include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    
    int n,sum;
    int *x;
    
    bool place(int t){
    	for(int i=0;i<t;++i){
    		if(x[i]==x[t] || (x[t]-t)==(x[i]-i) || (x[t]+t)==(x[i]+i))	
    			return false;
    	}
    	return true;
    }
    
    void backtrace(int t){
    	if(t>=n){
    		++sum;
    		for(int i=0;i<n;++i){
    			printf("%d ",x[i]);
    		}
    		printf("\n");
    	}else{
    		for(int i=0;i<n;++i){
    			x[t]=i;
    			if(place(t)) backtrace(t+1); 
    		}
    	}
    }
    
    int main()
    {
    	printf("please input the size: ");
    	scanf("%d",&n);
    	sum = 0;
    	x = (int *)malloc(n*sizeof(int));
    	backtrace(0);
    	printf("sum =  %d\n",sum);
    	free(x);		
    	return 0;
    }

n=8时，共有92种合法的放置法

2、Las Vegas法

当n=20时，传统的回溯法找到第一个解的时间大于2个半小时，耗时太长。

Las Vegas法是概率算法的一种，一般能获得更有效率的算法。

但是不时地要冒着找不到解的风险，算法要么返回正确的解，要么随机决策导致一个僵局。

n皇后的Las Vegas解，进行随机决策，一旦失败从头再来

QueensLv(success){//贪心的LV算法，所有皇后都是随机放置
    //若Success=true，则try[1..8]包含8后问题的一个解。
    	 col,diag45,diag135←Φ；//列及两对角线集合初值为空
    	 k ←0；//行号
    	 repeat    //try[1..k]是k-promising，考虑放第k+1个皇后
    	 	nb ←0；//计数器，nb值为（k+1)th皇后的open位置总数
    		for i ←1 to 8 do { //i是列号, 试探（k+1,i）安全否？
    	 	    if (i not in col) and (i-k-1 not in diag45) and (i+k+1 not in diag135) then{
    		            //列i对（k+1）th皇后可用，但不一定马上将其放在第i列
    		            nb ←nb+1；
    		            if uniform(1..nb)=1 then //或许放在第i列
                                j ←i；//注意第一次uniform一定返回1，即j一定有值i
    	           }//endif
    	      	}//endfor，在nb个安全的位置上随机选择1个位置j放置之
    	if(nb > 0) then{ //nb=0时无安全位置，第k+1个皇后尚未放好
    	//在所有nb个安全位置上，(k+1)th皇后选择位置j的概率为1/nb
            	k←k+1；//try[1..k+1]是(k+1)-promising 
                   	try[k] ←j；//放置(k+1)th个皇后
    	       	col ←col∪{ j }；
    	       	diag45 ←diag45 ∪{ j-k }；
    	       	diag135 ←diag135 ∪{ j+k }；
    	} //endif
       	until （nb=0）or（k=8）；//当前皇后找不到合适的位置或try是8-promising时结束。
       	success ← （nb>0）；
    }

代码：

#include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    int n;
    int *x;
    
    bool place(int t){
    	for(int i=0;i<t;++i){
    		if(x[t]==x[i] || (x[t]+t)==(x[i]+i)|| (x[t]-t)==(x[i]-i))
    			return false;
    	}
    	return true;
    }
    bool QueensLv(){
    	int nb,i,k,j;
    	k=0;
    	do{
    		nb = 0;
    		for(i=0;i<n;++i){
    			x[k]=i;
    			if(place(k)){
    				nb++;
    				if((int)(rand()*1.0/(RAND_MAX+1.0)*nb)+1==1)
    					j=i;
    			}
    		}
    		if(nb>0){
    			x[k]=j;
    			k++;
    		}
    	}while(nb !=0 && k!=8);
    	return (nb>0);
    }
    
    int main(){
    	srand((int)time(0));
    	printf("please input the size: ");
    	scanf("%d",&n);
    	x = (int *)malloc(n*sizeof(int));
    	bool re;
    	for(int i=0;i<100;++i){
    		re = QueensLv();
    		if(re) break;
    	}
    	printf(re==true ? "true\n":"false\n");
    	if(re == true){
    		for(int k=0;k<n;++k)
    			printf("%d ",x[k]);
    	}
    	free(x);
    }

3、回溯法和LV算法综合采用

消极：LV算法过于消极，一旦失败，从头再来  
乐观：回溯法过于乐观，一旦放置某个皇后失败，就进行系统回退一步的策略，而这一步往往不一定有效。   
折中：会更好吗？一般情况下为此

先用LV方法随机地放置前若干个结点，例如k个。然后使用回溯法放置后若干个结点，但不考虑重放前k个结点。  
stepVegas控制随机放置皇后的个数，代码：

#include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    #include <windows.h>
    
    #define RUN_TOTAL_TIME 100
    int n;
    int *x;
    bool sign;
    
    bool place(int t){
    	for(int i=0;i<t;++i){
    		if(x[t]==x[i] || (x[t]+t)==(x[i]+i)|| (x[t]-t)==(x[i]-i))
    			return false;
    	}
    	return true;
    }
    void backtrace(int t){
    	if(t>=n){
    		sign = true;
    	}else{
    		for(int i=0;i<n;++i){
    			x[t]=i;
    			if(place(t))
    				backtrace(t+1);
    		}
    	}
    }
    bool QueensLv(int stepVegas){
    	int nb,i,k,j;
    	k=0;
    	do{
    		nb = 0;
    		for(i=0;i<n;++i){
    			x[k]=i;
    			if(place(k)){
    				nb++;
    				if((int)(rand()*1.0/(RAND_MAX+1.0)*nb)+1==1)
    					j=i;
    			}
    		}
    		if(nb>0){
    			x[k]=j;
    			k++;
    		}
    	}while(nb !=0 && k!=stepVegas);
    	return (nb>0);
    }
    
    int main(){
    	srand((int)time(0));
    	printf("please input the size: ");
    	scanf("%d",&n);
    	x = (int *)malloc(n*sizeof(int));
    	bool re;
    	sign = false;
    	LARGE_INTEGER start,end,freq;
    	QueryPerformanceFrequency(&freq);
    	int successTime=0,stepVegas=0;
    	double totalTime=0;
    	while(stepVegas != n){
    		printf("stepVegas = ");
    		scanf("%d",&stepVegas);
    		successTime=0;
    		totalTime=0;
    		for(int i=0;i<RUN_TOTAL_TIME;++i){
    			QueryPerformanceCounter(&start);
    			re = QueensLv(stepVegas);
    			if(re) backtrace(stepVegas+1);
    			QueryPerformanceCounter(&end);
    			if(sign) {
    				++successTime;
    				totalTime += (double)(end.QuadPart-start.QuadPart)/(double)freq.QuadPart;
    				sign=false;
    			}
    		}
    		printf("The success rate is %.0f%% ; The average time is %.8f\n",
    		(successTime*1.0/RUN_TOTAL_TIME)*100,totalTime/successTime);
    	}		
    	free(x);
    	return 0;
    }

实验结果：

![Center 2][]

—表

[Center]: /images/20220714/5f8ffa52ede74371865e96c88095b34a.png
[Center 1]: /images/20220714/8f98388030ca4be5845f62d398e5e203.png
[Center 2]: /images/20220714/6ce145bec4074df1b4b4a42b1365aa3f.png