八皇后

思路

八皇后问题是很经典的递归回溯问题，就是在每一行尝试放置皇后，观察是否会冲突，这里就最简单粗暴的写出来解法吧。

#include <iostream>
#include <vector>

using namespace std;

/* 检查是否冲突 */
bool isVaild(vector<string>& board, int row, int col){
    int n = board.size();
    for(int i = 0; i < n; i ++)
        if(board[row][i] == 'Q')
            return false;
    for(int i = 0; i < n; i ++)
        if(board[i][col] == 'Q')
            return false;
    for(int i = row - 1, j = col + 1; i >= 0 && j < n; i --, j ++)
        if(board[i][j] == 'Q')
            return false;
    for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; i --, j --)
        if(board[i][j] == 'Q')
            return false;
    return true;
}

vector<string> ans;
void backTrack(vector<string>& board, int row, string s){
    if(row == (int)board.size()){
        ans.emplace_back(s);
        return;
    }
    /* 在每一行尝试放置皇后 */
    for(int i = 0; i < board[0].size(); i++){
        if(!isVaild(board, row, i))
            continue;
        board[row][i] = 'Q'; s.push_back(i + 1 + '0');
        backTrack(board, row + 1, s);
        /* 回溯 */
        board[row][i] = '.'; s.pop_back();
    }
}

int main(){
    int n;
    vector<string> board(8, string(8, '.'));
    string s = "";
    backTrack(board, 0, s);
    while(cin >> n){
        cout << ans[n - 1] << endl;
    }
}