算法基础班–第三章–1.2.1DFS——全排列搜索顺序(n皇后) ----另一种搜索顺序 见题解：更加原始的搜索顺序(n皇后)

算法模板

DFS 无模板，最重要是考虑问题的搜索顺序

本题完整代码：

#include <iostream>

using namespace std;

const int N = 20; //斜对角线 2n-1 所以开两倍N
int n;
char g[N][N];
bool col[N], dg[N], udg[N];// 同一列、对角线、斜对角线上只能有一个，分别记录的是该位置的列(斜)对角线上是否已经存在过，若均不存在，则填Q，并递归下一行

void dfs(int u) {
    if (u == n) { //有多少种满足条件的摆法就有多少次 u == n
        for (int i =0; i < n; i++) puts(g[i]);
        puts("");
        return ;
    }

    for (int i = 0; i < n; i++) //枚举第u行皇后该放在哪一列
        if (!col[i] && !dg[u + i] && !udg[i - u + n]) { // u+i和n-u+i怎么来的见图片
            g[u][i] = 'Q';
            col[i] = dg[u + i] = udg[n - u + i] = true; //更新状态
            dfs(u + 1);
            col[i] = dg[u + i] = udg[n - u + i] = false; // 恢复现场
            g[u][i] = '.';
        }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++ ) 
        for (int j = 0; j < n; j++ )
            g[i][j] = '.';
    dfs(0);
    return 0;
}