基础班笔记P58

dfs(0,0,0); //从左上角(0, 0)开始搜，记录当前共有多少个皇后（第三个参数代表当前皇后个数，初始是0）

#include <iostream>
#include <cstring>

using namespace std;

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

void dfs(int x, int y, int s) {
    if (y == n) x ++, y = 0; // y 出界，转到下一行第一个格子
    if (x == n) { //枚举到最后一行
        if (s == n) { // 如果此时摆的Q个数是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[n - x + y]) { //写成 y - x + n 不能AC，当n = 3时，不应该有答案，但是却有了错误答案
        g[x][y] = 'Q';
        row[x] = col[y] = dg[x + y] = udg[n - x + y] = true; //更新状态
        dfs(x , y + 1, s + 1);
        row[x] = col[y] = dg[x + y] = udg[n - 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); //从左上角(0, 0)开始搜，记录当前共有多少个皇后（第三个参数代表当前皇后个数，初始是0）

    return 0;
}