解法一

//做法1 观察到每一行都要放一个皇后，所以遍历每一行，找到满足条件的点放皇后
#include <iostream>

using namespace std;

const int N = 20; // 开2N因为，对角线的个数是2 * N - 1;

char g[N][N]; //棋盘
bool col[N],dg[N], udg[N]; //判断列、主副对角线上是否有皇后
//注意此方法不需要判断行上是否有皇后，因为我们是要找每一行上合法的位置放皇后
//所以在遍历每一行的每一列之前，每一行上是不会有皇后的
int n;

void dfs(int x) //x是行号，搜索每一行中可以放皇后的点
{
    if (x == n) //搜索完所有行了，此时一定放满了皇后，因为每行必须放一个皇后
    {
        for (int i = 0; i < n; i ++) puts(g[i]);
        puts("");
        return; //回溯
    }

    for (int y = 0; y < n; y ++ ) //遍历每一列，因为已知x，x是行号，我们要找到合适的列号放皇后
    {
        //如果该位置可以放皇后
        if(!col[y] && !dg[x - y + n] && !udg[x + y])
        {
            g[x][y] = 'Q';
            col[y] = dg[x - y + n] = udg[x + y] = true; //标记已经放过皇后
            dfs(x + 1); //搜索下一行
            //回溯后恢复现场
            col[y] = dg[x - y + n] = udg[x + y] = false;
            g[x][y] = '.';
        }
    }
}

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;
}

解法二

//做法二 不需要观察就能想到的做法
//从左上角往右下角遍历每一个格子，每一个格子都有两种做法：放皇后和不放皇后
//当遍历完所有格子的时候，问题就做完了

#include <iostream>

using namespace std;

const int N = 20;

int n;
char g[N][N]; //棋盘
bool row[N], col[N], dg[N], udg[N]; //相比做法1，需要判断行上有没有放过皇后
//因为做法一中，遍历每一行只能放一个皇后，而做法二是遍历每一个格子，所以要判断行上有无皇后

void dfs(int x, int y, int queen) //参数为(x,y)坐标和已经放的皇后个数
{
    //当遍历完同一行的每一列时
    if (y == n) y = 0, x ++;

    //当遍历完所有行 因为行号是从0到n-1
    if (x == n)
    {
        // 如果放完了皇后，说明找到了一种方法
        if(queen == n)
        {
            for (int i = 0; i < n; i ++) puts(g[i]);
            puts("");
        }
        return;
    }
    //对于每一个格子，有放和不放两种选择，我们搜一遍放的，搜一遍不放的
    //不放
    dfs (x , y + 1, queen);
    //放
    if (!row[x] && !col[y] && !dg[x - y + n] && !udg[x + y])
    {
        g[x][y] = 'Q';
        row[x] = col[y] = dg[x - y + n] = udg[x + y] = true;
        dfs(x, y + 1, queen + 1);
        row[x] = col[y] = dg[x - y + n] = udg[x + y] = false;
        g[x][y] = '.';
    }
}

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