关于N皇后问题的几种优化

N皇后问题定义

\(N\)皇后问题是指在\(N*N\)的棋盘上要摆\(N\)个皇后,要求任何两个皇后不同行,不同列也不再同一条斜线上,求不同的摆法数。

方法一

其实最容易想到的肯定是 DFS 暴搜了,不难写出如下代码:

bool check(vector<pair<int,int> > &pos,int x,int y){
    for(auto u:pos){
        int lx=u.first,ly=u.second;
        if(lx==x||ly==y) return false;
        if(abs(x-lx)==abs(y-ly)) return false;
    }
    return true;
}
int dfs(int re,vector<pair<int,int> > &pos,int n){
    if(re==0||pos.size()==n) return 1;
    int ans=0;
    for(int x=1;x<=n;++x) for(int y=1;y<=n;++y){
        if(check(pos,x,y)){
            vector<pair<int,int> > tmp=pos;
            tmp.push_back({x,y});
            ans+=dfs(re-1,tmp,n);
        }
    }
    return ans;
}
int Nqueen(int n) {
    vector<pair<int,int> > v;
    return dfs(n,v,n);
}

可以看到在 DFS 内部的枚举是十分低效的,因为每一次check()都需要\(O(n)\)的时间,所以在\(N=12\)左右就不太行了。

还有一个致命的问题就是,这个算法会导致重复方案的出现,虽然不难解决,但是一点都不优雅。

优化一

考虑到枚举下一个皇后时,我们使用了两个 for 循环来确定一个点,但是实际上由于题目的要求,我们实际上可以每次只枚举 \(x\) 坐标,然后 \(y\) 坐标是线性递增的。这样既可以解决重复计数的问题,也大大加快了算法速度。

bool check(vector<pair<int,int> > &pos,int x,int y){
    for(auto u:pos){
        int lx=u.first,ly=u.second;
        if(lx==x||ly==y) return false;
        if(abs(x-lx)==abs(y-ly)) return false;
    }
    return true;
}
int dfs(int re,vector<pair<int,int> > &pos,int n){
    if(re==0||pos.size()==n) return 1;
    int ans=0;
    for(int x=1;x<=n;++x){
        int y=re-1;
        if(check(pos,x,y)){
            vector<pair<int,int> > tmp=pos;
            tmp.push_back({x,y});
            ans+=dfs(re-1,tmp,n);
        }
    }
    return ans;
}
int Nqueen(int n) {
    vector<pair<int,int> > v;
    return dfs(n,v,n);
}

优化二

上面那个算法的瓶颈其实在于每次 DFS 过程中参数的传递,我们知道 vector 的常数是比较大的。那当然了我们也可以用数组来代替vector,但是众所周知在计算机中最快的操作就是位运算了,又由于这个问题的规模一般不会超过20,所以用位运算来表示哪些位置被占用是一个不错的方案。

具体而言:
\(row\)的第\(i\)位二进制为\(1\)就表示第\(i\)行已经被占用了;
\(l\)表示主对角线,它的第\(i\)位二进制为\(1\)表示在当前行之前这些位置在主对角线上已经有棋子了;
\(r\)表示副对角线,作用同上;

实测这样优化的话大搞可以在2s内跑个\(N=16\)的样子。

int dfs(int row,int l,int r,const int &mask){
    if(row==mask) return 1;
    int ans=0;
    for(int v=mask&(~(row|l|r)),p;v>0,p=v&(-v);v^=p)
        ans+=dfs(row|p,(l|p)<<1,(r|p)>>1,mask);
    return ans;
}
int Nqueen(int n) {
    return dfs(0,0,0,(1<<n)-1);
}

订阅评论
提醒
0 评论
内联反馈
查看所有评论