八皇后问题的优化

洛谷 DFS 优化 C++ 所有文稿

洛谷oj

最开始的做法

#include <iostream>
#include <cmath>
#include <string>
#include <string.h>
#include <set>
using namespace std;
int n,a[15],cnt=0,b[15],c[15];
set<string> se;
void solve(int cur){
    if (cur>n){
        cnt++;
        if(cnt<=3){
            bool sp=false;
            for(int i=1;i<=n;i++){
                if(sp) cout<<" ";
                else sp=true;
                cout<<a[i];
            }
            cout<<endl;
        }
        return;
    }
    for(int i=1;i<=n;i++){
        bool ok=true;
        for(int j=1;j<cur;j++) {if (a[j]==i||b[j]==cur-i||c[j]==cur+i) {ok=false;break;}}
        if(ok){
            a[cur]=i;
            b[cur]=cur-i;
            c[cur]=cur+i;
            solve(cur+1);
        }
    }
}
int main(){
    cin>>n;
    solve(1);
    cout<<cnt;
    return 0;
}

然而最后一个案例n=13超时了，回溯部分稍加修改：

for(int i=1;i<=n;i++){
        bool ok=true;
        for(int j=1;j<cur;j++) {if (a[j]==i||b[cur-i+n]||c[cur+i]) {ok=false;break;}}
        if(ok){
            a[cur]=i;
            b[cur-i+n]=true;
            c[cur+i]=true;
            solve(cur+1);
            b[cur-i+n]=false;
            c[cur+i]=false;
        }
}

直觉上并没有感觉会差多远，但是修改过后确实全部AC了

2019.4.1