题解 | 八皇后

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int N = 8;
int n=8;
int tem=0;
bool col[N],dg[2*N],undg[2*N];
//用来标记棋盘中的列、正对角线、副对角线上是否已经是其他皇后的击杀范围；
//主对角线编号是从左上往右下依次编号(0~2n-1);副对角线编号是从右上往左下依次编号(0~2n-1);
vector<int> strs;

void dfs(int r){
    if(r==n){
        strs.push_back(tem);
	  	return；//递归结束一定要记得return
    }
    for(int i=0;i<n;i++){
        if(!col[i] && !dg[r+i] && !undg[r-i+n]){
            tem=10*tem+i+1;
            dg[r+i]=undg[r-i+n]=col[i]=true;
            dfs(r+1);
            dg[r+i]=undg[r-i+n]=col[i]=false;
            tem=(tem-i-1)/10; //恢复上个串的状态
        }
    }
}

int main() {
    int x;
    dfs(0);
    sort(strs.begin(),strs.end());
    while (cin >> x) { // 注意 while 处理多个 case
        cout<<strs[x-1]<<endl;
    }
}
// 64 位输出请用 printf("%lld")

【dfs搜索思路】：一行肯定只能放一个皇后，所以解空间树的每层对应1行，每搜索到一层就遍历所有行，判断并记录皇后应该放到那一列；当遍历到第N行后，表示一条路径已经走到头了，回溯，然后尝试下一种摆放方式；

【关键点】：

1. 如果在第r行第i列放上了Q，那么第(r+i)个主对角线上就不能放了；第(r-i+n)个副对角线上也不能放了 ;