第一种搜索顺序（源自yxc: https://www.acwing.com/activity/content/code/content/47097/）

复杂度（O(n*n!)）

#include<iostream>
using namespace std;

const int N = 20;
int n;
char g[N][N];
int col[N], dg[N], udg[N];

void dfs(int u){
    if(u == n){
        for(int i=0; i<n; i++) puts(g[i]);
        puts(" ");
        return;
    }
    for(int i=0; i<n; i++)
        if(!col[i] && !dg[u+i] && !udg[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(){

    scanf("%d", &n);

    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            g[i][j] = '.';

    dfs(0);
    return 0;
}

第二种搜索顺序

复杂度O($2*($n^2))

#include<iostream>
using namespace std;

const int N = 20;
int n;
char g[N][N];
int row[N], col[N], dg[N], udg[N];
//一行一行遍历，y到边界后，位置到下一行第一个位置
//x-行 y-列  s-皇后数目
void dfs(int x, int y, int s)
{
    if(y == n) y = 0, x++;
    if(x == n){
        if(s == n){
            for(int i=0; i<n; i++) puts(g[i]);
            puts(" ");
        }
        return;
    }

    //不放皇后
    dfs(x, y + 1, s);
    //放皇后
    if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n])
    {
        g[x][y] = 'Q';
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;
        dfs(x, y + 1, s + 1);
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
        g[x][y] = '.';
    }
}

int main(){
    scanf("%d", &n);

    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            g[i][j] = '.';

    dfs(0, 0, 0);
    return 0;
}