n皇后

采用回溯法，以行为基准进行回溯，如果在当前行列放置皇后不会与已有皇后冲突，则放置，否则就不放置。

代码如下：

//
// Created by jt on 2020/9/29.
//
#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<string> > solveNQueens(int n) {
        vector<vector<string>> res;
        vector<int> vec;
        backtrace(res, vec, 0, n);
        return res;
    }

    void backtrace(vector<vector<string>> &res, vector<int> vec, int row, int n) {
        if (row == n) {
            vector<string> tmp;
            for (auto a : vec) {
                string s = string(n, '.');
                s[a] = 'Q';
                tmp.push_back(s);
            }
            res.push_back(tmp);
            return;
        }
        for (int col = 0; col < n; ++col) {
            vec.push_back(col);
            if (!detectConflict(vec)) backtrace(res, vec, row+1, n);
            vec.pop_back();
        }
    }

    bool detectConflict(vector<int> &vec) {
        int curRow = vec.size() - 1, curCol = vec[vec.size()-1];
        for (int row = 0; row < vec.size() - 1; ++row) {
            // 判断是否同一直线上
            if (vec[row] == curCol) return true;
            // 判断是否在左侧或右侧斜线上
            if (curRow - row == abs(curCol - vec[row])) return true;
        }
        return false;
    }
};