八皇后

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> A;
int Q[8][8] = {0};

//因为是从上往下，当前行下面不会有元素，所以只需要判断左上角和右下角
bool Judge(int row, int col)
{
    for(int i = 0; i < 8; ++i) //判断列
    {
        if(Q[i][col] == 1)
            return false;
    }
    for(int i = row, j = col; i >= 0 && j >= 0; --i, --j) //判断左上角
    {
        if(Q[i][j] == 1)
            return false;
    }
    for(int i = row, j = col; i >= 0 && j < 8; --i, ++j) //判断右上角
    {
        if(Q[i][j] == 1)
            return false;
    }
    return true;
}

void DFS(int row, int ans)
{
    if(row == 8)
    {
        A.push_back(ans);
        return;
    }
    for(int col = 0; col < 8; ++col) //考虑所有邻居
    {
        if(Judge(row, col))
        {
            Q[row][col] = 1;
            DFS(row+1, ans*10 + col+1);
            
            Q[row][col] = 0; //回退
        }
    }
}

int main()
{
    DFS(0, 0);
    sort(A.begin(), A.end());
    int index;
    while(scanf("%d", &index) != EOF)
    {
        cout << A[index-1] << endl;
    }
}