1. 题目简介

原题链接：843. n-皇后问题

n皇后问题，填棋子方案，要求每一行，每一列，每一对角线不能有两个棋子。

算法标签：DFS、n皇后问题。

技巧：对角线的表示、搜索恢复现场（回溯）。

2. 题解代码

• 通过bool数组col[N]、dg[N]、 udg[N]分别表示列、主对角线、副对角线是否有棋子。
• 主对角线的表示：$y = x + b$；副对角线的表示：$y = -x + b$。
• 上面两种对角线都用截距 $b$ 表示，为了防止出现负数，主对角线截距加一个偏移量,即 $b = x - y + n$。

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 20;

char g[N][N];       // 棋盘数组
int path[N];        // 搜索路径
bool col[N], dg[N], udg[N]; // 判断垂直、正对角线、副对角线位置状态
int n;

void dfs(int x) {   // 一行一行搜索
    if(x == n) {    // DFS搜索到底了,开始输出
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(j == path[i])    cout << 'Q';
                else    cout << '.';
            }
            cout << endl;
        }
        cout << endl;
    }    
    for(int y = 0; y < n; y++) {    // 遍历每行的各个位置
        if(!col[y] && !dg[x + y] && !udg[y - x + n]) {  // 对角线与副对角线下标由截距表示
            path[x] = y;
            col[y] = dg[x + y] = udg[y - x + n] = true;
            dfs(x + 1);
            col[y] = dg[x + y] = udg[y - x + n] = false;// 恢复现场           
        }        
    }
}

int main() {
    cin >> n;
    dfs(0);

    return 0;
}