$\Huge\color{orchid}{点击此处获取更多干货}$

DFS

同为深搜回溯的经典问题，相比数字排列，n皇后问题中如果还按照数字排列的方式去枚举皇后可能出现的位置，那么对于$n^2$大小的棋盘，时间复杂度可能会达到$O(n^2!)$，$n$就算取4，$16!$的数量级也可以达到$10^{13}$，连有可行方案的最小n都没法在规定时间之内得出所有可行方案，那么我们换一种方式，皇后不能互相攻击的条件是n个皇后处于不同行、不同列、主副对角线上分别不同的斜线，取其中一个限制条件枚举（比如行），那只要判断剩下三个限制条件是否满足，就能判断下一个皇后的摆放位置，这样就可以把时间复杂度控制在$O(n!)$

下面解释一下主副对角线，阶数为$n$的矩阵有两条对角线，行列号相等的叫主对角线，行列号相加之和等于$n+1$的是副对角线，其余对角方向的斜线上，与主对角线平行的视作主对角线方向，其上的矩阵元素行号与列号的差值可以区分这些斜线；与副对角线平行的视作副对角线，其上元素行列号的和可以区分这些斜线，由于主对角线方向上，行列号差值可能是负数，因此对于这个，有两种解决方式，一种是官方视频中的“正向偏移$n$用数组表示”，还有一种更直观的方式就是用哈希表保存，本帖中就使用哈希表，保存出现了皇后的主副对角线区分指标

C++ 代码

#pragma GCC optimize(2)
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <unordered_set>
using namespace std;

vector<string> board;
bool* col;//记录每一列是否有其他皇后
//记录主副对角线方向上是否有其他皇后
//主对角线方向用r-c确定，副对角线方向用r+c确定
unordered_set<int> mainDiag, subDiag;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    board.resize(n, string(n, '.'));
    col = new bool[n];
    fill(col, col + n, false);
    //lambda表达式递归的另一种写法就是将函数对象自身作为参数
    auto dfs = [&](auto&& dfs, int r)-> void {  //按行枚举，已枚举的行数为搜索树深度
        //最大行数为搜索树叶子节点位置
        if (r == n) {
            for (int i = 0; i < n; i++) {
                cout << board[i] << endl;
            }
            cout << endl;
            return;
        }
        //枚举这一行的每一列
        for (int c = 0; c < n; c++) {
            if (col[c]                                  //同一列有皇后
            || mainDiag.find(c - r) != mainDiag.end()   //主对角线方向有皇后
            || subDiag.find(c + r) != subDiag.end()) {  //副对角线方向有皇后
                continue;
            }
            //上述条件都不满足，就在当前位置放个皇后
            board[r][c] = 'Q';
            //然后在列，主对角线，副对角线上都记录下来
            col[c] = true;
            mainDiag.insert(c - r);
            subDiag.insert(c + r);
            //进入搜索树的更深一层
            dfs(dfs, r + 1);
            //回溯，恢复现场
            board[r][c] = '.';
            col[c] = false;
            mainDiag.erase(c - r);
            subDiag.erase(c + r);
        }
    };
    //刚开始一个皇后都没有，枚举行数是0
    dfs(dfs, 0);
    delete[] col;
    return 0;
}