利用概率算法求解八皇后问题

2016-10-20

但是当皇后的数量较多时，回溯法非常地耗时。所以提出了一种基于概率地随机放置皇后的方法。

每次都将8个皇后随机放在8行，如果满足条件就成功，否则全部重新放置，直到成功为止。

实验表明，这样地放置方法比回溯法更快。

还有一种优化就是对于一部分皇后随机放置，另一部分皇后采用回溯法放置，这样效果会更好。

代码

#include"stdio.h"
#include"stdlib.h"
#include"assert.h"
#include"time.h"

#define MAX 500
int check_pos(const int r[MAX],const int i,const int j);
void print(const int r[MAX],const int n);
int queen_lv(int r[MAX],const int n);

int main(int argc,char *argv[]){
    if(argc!=2){
        fprintf(stderr,"Please input the number of queen!\n");
        return 0;
    }
    int n=atoi(argv[1]);
    if(n<4){
        fprintf(stderr,"The number of queen must be larger than 4 !\n");
        return 0;
    }
    srand((unsigned int)time(NULL));
    int results[MAX];   // results[i]=j，表示把第i个皇后放在位置(i,j)上
    while(queen_lv(results,n)==0)
        ;     //一直随机放，直到存在一个解
    // print(results,n);
    return 0;
}

//所有皇后的位置都是随机放的
int queen_lv(int r[MAX],const int n){
    int num=0;
    int i,j,k,nb;
    i= 0;
    while(1){
        nb = 0; //第i个皇后可以放的位置的数量
        for(j=0;j<n;j++){  // 试探0-7的位置对于第 i 个皇后来说是否可以放置
            if(check_pos(r,i,j)){
                nb++;
                if(rand()%nb+1 == 1) //以 1/nb 的概率将第i个皇后放在j列上
                    k=j;
            }
        }
        if(nb>0){  //放置第i个皇后的位置，并继续放下一个皇后
            r[i++] = k;
        }
        if(nb==0 || i==n)
            break;
    }
    if(nb>0)  
        return 1; //成功了
    else
        return 0;//如果第i个皇后没有可行的位置，则这次随机过程失败，完全重新开始放置
}

//第i个皇后放在(i,j)位置是否合适
int check_pos(const int r[MAX],const int i,const int j){
    int k;
    for(k=0;k<i;k++){
        if(r[k] == j) //是否在同列
            return 0;
        if(r[k]+k == i+j) //是否在45度对角线
            return 0;
        if(r[k]-k == j-i) //是否在135度对角线
            return 0;
    }
    return 1;
}
//打印皇后放置的位置
void print(const int r[MAX],const int n){
   //省略，参考之前的代码
}

结果

分别利用回溯法和 Las Vegas 概率算法求解 n 皇后问题的一个解，对它们所耗的时间进行比较。

当 n=8 时，回溯法 0.084ms，Las Vegas 概率算法 0.029 ms。

当 n=20 时，回溯法 133.581ms，Las Vegas 概率算法 9.314 ms。

改进

Las Vegas 概率算法每次放置皇后的位置都是随机的，这样过于悲观。可以使用 Las Vegas 算法放置前一部分的皇后，后面的皇后使用回溯法放置，但不考虑重放前面通过 LV 算法放置的皇后。

代码实现方面只要将后面的几行改为：

if(nb = 0 || i = stepVegas) //跳出循环
    break;
...
if(nb>0)  //已随机放好stepVegas个皇后
    backtrace(); //采用回溯法放后面的皇后
else
    return 0;

改进后的代码：

#include"stdio.h"
#include"stdlib.h"
#include"assert.h"
#include"time.h"

#define MAX 500

int check_pos(const int r[MAX],const int i,const int j);
void print(const int r[MAX],const int n);
int queen_lv(int r[MAX],const int n,const int sv);
int backtrace(int r[MAX],const int n,int start);

int main(int argc,char *argv[]){
    if(argc!=3){
        fprintf(stderr,"Please input the number of queen and vs!\n");
        return 0;
    }
    int n=atoi(argv[1]);
    if(n<4){
        fprintf(stderr,"The number of queen must be larger than 4 !\n");
        return 0;
    }
    int sv=atoi(argv[2]);
    srand((unsigned int)time(NULL));
    int results[MAX];   // results[i]=j，表示把第i个皇后放在位置(i,j)上

    while(queen_lv(results,n,sv)==0)
        ;     //一直随机放，直到存在一个解

    //print(results,n);
    return 0;
}

// 前vs个皇后随机放置
int queen_lv(int r[MAX],const int n,const int sv){
    int num=0;
    int i,j,k,nb;
    i= 0;
    while(1){
        nb = 0; //第i个皇后可以放的位置的数量
        for(j=0;j<n;j++){  // 试探0-7的位置对于第 i 个皇后来说是否可以放置
            if(check_pos(r,i,j)){
                nb++;
                if(rand()%nb+1 == 1) //以 1/nb 的概率将第i个皇后放在j列上
                    k=j;
            }
        }
        if(nb>0){  //放置第i个皇后的位置，并继续放下一个皇后
            r[i++] = k;
        }
        if(nb==0 || i==sv)
            break;
    }
    if(nb>0)  
        return backtrace(r,n,sv+1); //成功了
    else
        return 0;//如果第i个皇后没有可行的位置，则这次随机过程失败，完全重新开始放置
}

//利用回溯法从第start个皇后开始放，前start-1个已经放好了
int backtrace(int r[MAX],const int n,int start){
    int i,j,num;
    i=start;j=0,num=0;
    while(1){
        int find=0;
        while(j<n){    // 寻找第i个皇后放置的位置j
            if(check_pos(r,i,j))
                break;
            j++;
        }
        if(j<n){      // 如果找到了记录该位置，继续放置第i个皇后
            r[i++] = j;
            j = 0;
        }else{        // 如果没有找到合适的位置，回溯到第i-1个皇后，将其位置放在原来位置的下一个位置
            j = r[--i] + 1 ;
        }
        if(i == n && r[i-1]<n){ //找到了一个合适的解
            //print(r,n);
            j=r[--i]+1;
            num++;
            return num; //找到一个解就返回
        }else if(i<start)  //已经找到了全部的解
            break;
    }    
    return num;
}
//第i个皇后放在(i,j)位置是否合适
int check_pos(const int r[MAX],const int i,const int j){
    //省略，参考之前的代码
}
//打印皇后放置的位置
void print(const int r[MAX],const int n){
   //省略，参考之前的代码
}