题解 | 八皇后——实现了N皇后，可以套用模板，输入n=8即可；

经典回溯问题：N皇后。把N皇后的代码背下来，修改修改即可。

解法：定义全局变量boardSize,用来控制棋盘大小，此处boardSize=8

另外写了一个init()函数，用来构造8*8的棋盘。

其他思路完全同N皇后，定义string path来存放一次成功的摆放方案，vector<string>res来存放所有的path。

最后只需要sort(res.begin(),res.end(),myCompare); 对res排序完毕后按给出的下标 i 输出相应位置的res[i-1]即可。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


int boardSize;
string path;
vector<string> res;
vector<vector<char>> chessboard;

void init(){
    chessboard=vector<vector<char>>(boardSize,vector<char>(boardSize,'0'));
}

// 判断当前放上皇后的棋盘是否合法
bool islegal(int row, int col) {
    //当前应该在第row行放置皇后，皇后的位置在第col列
    //判断竖排
    for (int i = 0; i < row; i++) {
        if (chessboard[i][col] == 'Q') return false;
    }
    // 左上45°
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
        if (chessboard[i][j] == 'Q') return false;
    }
    // 右上45°
    for (int i = row - 1, j = col+1 ; i >= 0 && j < chessboard.size(); i--, j++) {
        if (chessboard[i][j] == 'Q') return false;
    }
    return true;
}

//输入包括当前棋盘，以及当前放到第i个位置
void BackTrack(int index) {
    if(index==chessboard.size()){
        res.push_back(path);
        return;
    }
    for(int j=0;j<chessboard.size();j++){
        if(islegal(index,j)){
            path.push_back(j+1+'0');
            chessboard[index][j]='Q';
            BackTrack(index+1);
            chessboard[index][j]='0';
            path.pop_back();
        }
    }
}

bool myCompare(const string &a,const string &b){
    return a<b;
}
int main() {  
    boardSize=8; //修改这里的boardSize即可改变棋盘
    init();
    BackTrack(0);
    sort(res.begin(),res.end(),myCompare);

    int num;
    while(cin>>num){
        cout<<res[num-1]<<endl;
    }

    
}
// 64 位输出请用 printf("%lld")