N皇后问题

N皇后是很经典的回溯算法题，类似的题目还有 https://leetcode-cn.com/problems/sudoku-solver/ （解数独），回溯法的思路类似DFS，
解决一个回溯问题，实际上就是一个决策树的遍历过程。 这类问题要考虑以下几点
1、路径：也就是已经做出的选择。
2、选择列表：也就是你当前可以做的选择。
3、结束条件：也就是到达决策树底层，无法再做选择的条件。
我认为，回溯法其实就是一种穷举，时间复杂度一般都很高，N皇后问题的回溯法复杂度已经达到了O(n!),我的代码如下

#include<iostream>
#include<vector>
using namespace std;

/*0表示可以放棋子 1表示进入攻击范围 2表示该位置有皇后*/
typedef vector<int> vi;
typedef vector<vi> v2d;
typedef vector<v2d> v3d;
typedef pair<int, int> P;

v3d result;

void mark(v2d& chessboard, int i, int j) {
    int n = chessboard.size();
    for (int k = 0; k < n; k++) {   //横纵标记
        chessboard[i][k] = 1;
        chessboard[k][j] = 1;
    }
    int t1 = i + 1;
    int t2 = j + 1;
    while (t1 < n && t2 < n) {
        chessboard[t1][t2] = 1;
        t1++;
        t2++;
    }
    t1 = i - 1;
    t2 = j - 1;
    while (t1 >=0 && t2 >= 0) {
        chessboard[t1][t2] = 1;
        t1--;
        t2--;
    }
    t1 = i - 1;
    t2 = j + 1;
    while (t1 >= 0 && t2 < n) {
        chessboard[t1][t2] = 1;
        t1--;
        t2++;
    }
    t1 = i + 1;
    t2 = j - 1;
    while (t1 < n && t2 >= 0) {
        chessboard[t1][t2] = 1;
        t1++;
        t2--;
    }
    chessboard[i][j] = 2;
}
 
void dfs(v2d chessboard, int n, int row) {
   /* cout << endl;
    for (auto td : chessboard) {
        for (auto t : td)  cout << t;
        cout << endl;
    }*/
    vi psblist;  //可以放皇后的点集,只存纵坐标
    if (chessboard.size() == 0) {   //新建棋盘
        for (int i = 0; i < n; i++) {
            vi t(n, 0);
            chessboard.push_back(t);
        }
        for (int i = 0; i < n; i++) {
            psblist.push_back(i); //新棋盘取第一行作为回溯点集
        }
    }
    else {
        for (int i = 0; i < n; i++) {
            if (chessboard[row][i] == 0) psblist.push_back(i);
        }
    }
    for (auto j: psblist) {
        v2d huishu = chessboard;
        mark(huishu, row, j);
        if (row == n - 1) {
            result.push_back(huishu);   return;
        }
        else {
            dfs(huishu, n, row + 1);
        }
    }
}

vector<vector<string>> solveNQueens(int n) {
    if (n == 0)    return {};
    v2d chessboard;
    dfs(chessboard, n, 0);
    vector<vector<string>> rt;
    for (auto oneres : result) {    //转换
        vector<string> cb;
        for (auto td : oneres) {
            string line = "";
            for (auto t : td) {
                if (t == 2)    line += "Q";
                else  line += ".";
            }
            cb.push_back(line);
        }
        rt.push_back(cb);
    }
    return rt;
}