按行dfs

#include <iostream>
using namespace std;
const int N = 20;
char g[N][N];   //棋盘矩阵，存路径
bool col[N];    //判断该列是否有出现过的棋子
bool dg[N];     //判断该正斜线\是否有出现过的棋子
bool udg[N];    //判断该反斜线/是否有出现过的棋子
int n;
void dfs(int u) //第u行，一行行来执行
{
    if(u == n){
        for(int i = 0; i < n; ++i)
            puts(g[i]); //直接输出二维矩阵g的g[i]
        puts("");
    }
    else{//(x,y)相当于(u,i),c++中坐标轴是反的，因此要注意
        for (int i = 0; i < n; ++i) {//dg[u+i]表示y=-x+b,b=x+y,即正斜线，同一正斜线上所有的x+y即u+i都相等，反斜线同理，但是由于下标是正的，所以要加上一个偏移量n,即b=n-u+i,反斜线上所有格子的b也相等
            if (!col[i] && !dg[u + i] && !udg[n - u + i]) { //如果列上，正反斜线上都为空，剪枝操作
                col[i] = dg[u + i] = udg[n - u + i] = true;
                g[u][i] = 'Q';//修改状态，表示该位置已经有棋子
                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;
}

按格子dfs

#include <iostream>//更加接近问题本质的方式,一个格子一个格子地dfs，一个格子只有放与不放两种选择
using namespace std;//搜索策略和搜索顺序的不同会导致不同的时间复杂度和结果
const int N = 20;
char g[N][N];
bool col[N], cow[N], dg[N], udg[N];//一个个搜索，所以加上行cow[]
int n;
void dfs(int x, int y, int s)//(横坐标，综坐标，状态)棋盘上有k个棋子则s = k
{//分为x == n 和 y == n两种情况
    if(y == n){//如果一列横着搜索完就跳到下一行，并从y = 0开始搜索
        ++ x;
        y = 0;
    }
    if(x == n){//x,y等于n的时候，实际上x,y已经出界了，所以x==n时必定枚举完了
        if(s == n){//因为是一个个枚举，所以会出现到最后s!=n的情况，所以要加上s==n的判断
            for(int i = 0; i < n; ++i)
                puts(g[i]);
            puts("");
        }
        return;
    }
    else{
        if(!col[y] && !cow[x] && !dg[x + y] && !udg[n - x + y]){//如果该位置可以放棋子，即横竖斜都为空
            col[y] = cow[x] = dg[x + y] = udg[n - x + y] = true;
            g[x][y] = 'Q';  //修改状态
            dfs(x, y + 1, s + 1);   //放下棋子，然后继续dfs搜索下一个格子
            col[y] = cow[x] = dg[x + y] = udg[n - x + y] = false;   //恢复现场
            g[x][y] = '.';
        }
        dfs(x, y + 1, s);   //不放棋子，继续搜索下一个格子
    }
}
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;
}