题解 | #八皇后#

DFS搜索，从小往大搜自然满足题目的顺序要求

#include <iostream>
#include <cstring>
using namespace std;

int queens[8];
int cnt=0;
bool visit[8];

bool islegal(int index,int i){  //判断新加的皇后会不会被斜着吃掉
    for(int k=0;k<index;k++){  //遍历已经排好位置的皇后
        if((index-k)==(i-queens[k]) || \  //y=x or y=-x 在斜线上
           (index-k)==(queens[k]-i))
            return false;
    }
    return true;
}

void getnth(int n,int index){  //DFS递归函数
    if(index==8){  //递归出口
        cnt++;
        if(cnt==n){
            for(int i=0;i<8;i++)
                cout<<queens[i]+1;
            cout<<endl;
        }
        return;
    }
    for(int i=0;i<8;i++){  //假定当前棋子index应该在位置i，引出八个分支并且剪枝
        if(visit[i]){  //剪掉新加的皇后被直着吃的分支
            continue;
        }
        if(islegal(index,i)){ //剪掉新加皇后被斜着吃的分支
            visit[i]=true;
            queens[index]=i;
            getnth(n,index+1);  //开分支，确定下一个皇后的位置
            visit[i]=false;
        }
    }
}

int main(){
    int n;
    while(cin>>n){
        memset(queens,0,sizeof(queens));
        memset(visit,false,sizeof(visit));
        cnt=0;
        getnth(n,0);
    }
}