dfs-n皇后排列问题

重点
1. 搜索树的节点是一个棋盘的局面
2. dfs(u)表示搜索第u行的皇后的所有可能局面
3. 对每种肯恩局面进行递归搜索，对不可能的局面进行剪枝，即没有必要继续向下搜索

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 15;
char q[N][N];
int n;
bool l[20], r[20];
bool st[N];

void dfs(int u) {  
    if (u == n) {  //搜索到了树的叶子，即整个局面搜索完成
        for (int i = 0; i < n; i++) puts(q[i]);
        puts("");
        return ;
    }
    for (int i = 0; i < n; i++) {
        if (st[i] || l[i - u + n] || r[i + u]) continue;//剪枝，这里利用同一条直线截距相同的原理
        st[i] = l[i - u + n] = r[i + u] = true;
        q[u][i] = 'Q';
        dfs(u + 1);

        q[u][i] = '.';
        st[i] = l[i - u + n] = r[i + u] = false;
    }

}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            q[i][j] = '.';
        }
    }
    dfs(0); // 搜索第0个位置的数

    return 0;
}