题解 | #八皇后# DFS清晰注解

#include <iostream>
#include<vector>
using namespace std;
vector<int>res;
vector<vector<int>>board(8,vector<int>(8,0));   //棋盘

bool judge(int x,int y){    //能否放置
    for(int i=0;i<x;i++){      
        if(board[i][y]) return false;   //判断列(行无须判断)
        int j=i+y-x;
        if(j>=0 && board[i][j]) return false;     //判断两对角
        j=x+y-i;
        if(j<8 && board[i][j]) return false;
    }
    return true;
}

void dfs(int x,int y,int cur){      //x,y为当前尝试放置的坐标
    if(judge(x,y)){        //可放置
        if(x==7) {
            res.push_back(cur*10+(y+1));     //已经是最后一行，直接添加结果并返回
            return;
        }
        else{                           //不是最后一行
            board[x][y]=1;              //放置当前坐标下
            dfs(x+1,0,cur*10+(y+1));    //尝试放在下一行第一个
            board[x][y]=0;      //回溯，该格设为不放置
        }
    }
    if(y!=7)  dfs(x,y+1,cur);  //无论当前该格可不可以放置，都尝试放在下一格
}

int main() {
    dfs(0,0,0);
    int n;
    while(cin>>n){
        cout<<res[n-1]<<endl;
    }
}