八皇后

题目所给用例输入有误，以输入用例描述为准：每组测试数据占1行，包括一个正整数b(1 <= b <= 92)，改为

1
92

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
#include <string>
using namespace std;
//输入棋盘边长n,返回所有合法的放置
vector<string> res;
bool isValid(vector<string>& board, int row, int col);
void backtrack(vector<string> &board, int row);

void solveNQueens(int n){
    //'.'表示空，'Q'表示皇后，初始化空棋盘
    vector<string> board(n, string(n, '.'));
    backtrack(board, 0);
}
string ans = "";
//路径：board小于row的那些行都已经成功放置了皇后
//选择列表：第row行的所有列都是放置皇后的选择
//结束条件：row超过board的最后一行
void backtrack(vector<string> &board, int row){
    //触发结束条件
    if(row == board.size()){
        res.push_back(ans);
        return;
    }

    int n = board[row].size();
    for(int col = 0; col < n; col++){
        //排除不合法选择
        if(!isValid(board, row, col))
            continue;
        //做选择
        board[row][col] = 'Q';
        ans.push_back(char(col + '1'));
        //进入下一行决策
        backtrack(board, row + 1);
        ans.pop_back();
        //撤销选择
        board[row][col] = '.';
    }
}

//是否可以在board[row][col]放置皇后
bool isValid(vector<string>& board, int row, int col){
    int n = board.size();
    //检查列是否有皇后互相冲突
    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;
}
int main(){
    solveNQueens(8);
    int b;
    while(~scanf("%d", &b)){
        cout << res[b - 1] << endl;
    }
    return 0;
}