P1219 八皇后问题题解

题目传送门

#include 

using namespace std;
const int N = 100;
int a[N], n, ans;
int b1[N];//列桶
int b2[N];//正对角线桶
int b3[N];//反对角线桶

//解决：第x行的皇后放在哪里？
void dfs(int x) {
    if (x == n + 1) {
        //方案数量
        ans++;
        if (ans <= 3) {
            for (int i = 1; i <= n; i++) printf("%d ", a[i]);
            printf("\n");
        }
        return;
    }
    //尝试在第i列放入皇后
    for (int i = 1; i <= n; i++) {
        //因为x上按行一行一行来的，所以不用考虑行的冲突，只需要考虑列、正对角线，反对角线三个方向
        //b2[x+i] 因为同一正角线的位置，行+列是相等的，如果我们设置了 行+列使用过了，
        //那么，其它再检查到同一对角线时，就会发现行+列已使用过
        //b3[x - i + 15] 因为同一反对角线的位置，行-列是相等的，但可能行>列，也可能列>行，
        //这要看它是最长对角线的右上方还是左下方，右上方x>y,左下方x> n;
    //放第几行
    dfs(1);
    //输出大吉
    printf("%d\n", ans);
    return 0;
}