【正经题解】八皇后-1

使用一个长度为 $10$ 的数组 $a$ 来存储每一行皇后所在的列号。
使用三个数组 $b$ , $c$ , $d$ 分别表示列、左斜对角线、右斜对角线上是否有皇后。
递归搜索每一行的皇后放置位置，保证在同一列、同一左斜对角线、同一右斜对角线上没有重复。
当找到一个解时，输出当前解的信息。

#include <bits/stdc++.h>
using namespace std;

int a[10], b[10], c[20], d[20], sum;

// 输出当前解的信息
void printSolution() {
    cout << "sum=" << sum << endl;
    for (int i = 1; i <= 8; i++)
        cout << " " << a[i];
    cout << endl;
}

// 搜索八皇后问题的解
void dfs(int t) {
    if (t == 9) {
        sum++;
        printSolution(); // 找到解时输出
        return;
    }
    for (int i = 1; i <= 8; i++) {
        // 检查当前位置是否合法
        if (!b[i] && !c[i - t + 8] && !d[i + t]) {
            a[t] = i;
            b[i] = c[i - t + 8] = d[i + t] = 1; // 标记当前位置已经被占用
            dfs(t + 1); // 递归搜索下一层
            a[t] = b[i] = c[i - t + 8] = d[i + t] = 0; // 恢复状态，尝试其他可能性
        }
    }
}

int main() {
    dfs(1);
    return 0;
}