洛谷 P1219 八皇后 Checker Challenge

// 第 ① 版：把第 4 章那份 N 皇后原样搬过来
//
// 两处和第 4 章不一样，而这道题的分全在这两处：
//   ⚠ 一、**它输出了所有解** —— 而题目只要**前三个**，第四行是解的总数。
//      ★ 这一处**样例就能挡住**：n = 6 有 4 个解，它会打 5 行（4 个解 + 总数），
//        标准答案是 4 行（3 个解 + 总数）。
//   ⚠ 二、判「这一格能不能放」用的是「和前面每个皇后逐个比一遍」，
//      也就是每放一格要花 O(行号) 的时间。n = 13 时这笔账不小 —— 见第 ③ 版。
//
// 输入：一行一个整数 n（6 ≤ n ≤ 13）。

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

int n;
int pos_[20];                 // pos_[r] = 第 r 行的皇后放在第几列
long long total_ = 0;

/** 第 r 行放在第 c 列合不合法：和前面每一个皇后比一遍 */
bool ok(int r, int c) {
    for (int i = 1; i < r; i++) {
        if (pos_[i] == c) return false;              // 同列
        if (abs(pos_[i] - c) == r - i) return false; // 同对角线（行差 == 列差）
    }
    return true;
}

void dfs(int r) {
    if (r > n) {
        total_++;
        for (int i = 1; i <= n; i++)                 // ⚠ 有多少解就打多少行
            cout << pos_[i] << (i == n ? '\n' : ' ');
        return;
    }
    for (int c = 1; c <= n; c++) {
        if (!ok(r, c)) continue;
        pos_[r] = c;
        dfs(r + 1);                                  // ★ 这一版连「撤销」都不用写：
                                                     //   pos_[r] 下一轮会被直接盖掉
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    dfs(1);
    cout << total_ << '\n';
    return 0;
}

// 第 ② 版：格式改对了 —— 只打前三个解
//
// 改动只有一行半：加一个「已经打了几个」的计数器，够三个就不打了。
// ⚠ **不能「找够三个就 return」** —— 第四行还要输出解的**总数**，
//   所以搜索必须走完，只是不再往外打。
//
// ★ 这一版**已经能 AC 了**（本机 n = 13 实测 0.71 秒，题目限时 1 秒）——
//   但这个余量薄得吓人，正文第 ④ 步把它拆开看。

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

int n;
int pos_[20];
long long total_ = 0;
int printed = 0;

bool ok(int r, int c) {
    for (int i = 1; i < r; i++) {
        if (pos_[i] == c) return false;
        if (abs(pos_[i] - c) == r - i) return false;
    }
    return true;
}

void dfs(int r) {
    if (r > n) {
        total_++;
        if (printed < 3) {                           // ★ 只打前三个，但**不能提前收工**
            printed++;
            for (int i = 1; i <= n; i++)
                cout << pos_[i] << (i == n ? '\n' : ' ');
        }
        return;
    }
    for (int c = 1; c <= n; c++) {
        if (!ok(r, c)) continue;
        pos_[r] = c;
        dfs(r + 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    dfs(1);
    cout << total_ << '\n';
    return 0;
}

// 换一把尺子：三种判法各自走了多少个节点
//
// ★★ 这一章最反直觉的一件事，就是靠它量出来的：
//   **三种写法走的是同一棵搜索树，节点数一个都不差** —— 差的只是「每个节点多贵」。
//   ⇒ 本书一贯的做法是「秒表量不动就换尺子数次数」，
//     而这道题**正好反过来：数次数完全看不出差别，只有秒表分得出**。
//
// 用法：./p1219Count <n>        打三种判法的节点数和解的个数
//       ./p1219Count <n> csv    只打 `键,值`，给 check:viz 用

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

int n;
long long nodesA = 0, nodesB = 0, nodesC = 0;
long long totA = 0, totB = 0, totC = 0;
int pos_[20];
bool col[20], d1[40], d2[40];
int full_;

bool ok(int r, int c) {
    for (int i = 1; i < r; i++) {
        if (pos_[i] == c) return false;
        if (abs(pos_[i] - c) == r - i) return false;
    }
    return true;
}
void dfsA(int r) {
    nodesA++;
    if (r > n) { totA++; return; }
    for (int c = 1; c <= n; c++)
        if (ok(r, c)) { pos_[r] = c; dfsA(r + 1); }
}
void dfsB(int r) {
    nodesB++;
    if (r > n) { totB++; return; }
    for (int c = 1; c <= n; c++) {
        if (col[c] || d1[r + c] || d2[r - c + n]) continue;
        col[c] = d1[r + c] = d2[r - c + n] = true;
        dfsB(r + 1);
        col[c] = d1[r + c] = d2[r - c + n] = false;
    }
}
void dfsC(int r, int c, int l, int rr) {
    nodesC++;
    if (r > n) { totC++; return; }
    int avail = full_ & ~(c | l | rr);
    while (avail) {
        int p = avail & -avail;
        avail -= p;
        dfsC(r + 1, c | p, (l | p) << 1, (rr | p) >> 1);
    }
}

int main(int argc, char** argv) {
    n = (argc > 1) ? atoi(argv[1]) : 8;
    bool csv = (argc > 2 && string(argv[2]) == "csv");
    full_ = (1 << n) - 1;
    dfsA(1);
    dfsB(1);
    dfsC(1, 0, 0, 0);
    if (csv) {
        cout << "n," << n << '\n';
        cout << "solutions," << totA << '\n';
        cout << "nodesA," << nodesA << '\n';
        cout << "nodesB," << nodesB << '\n';
        cout << "nodesC," << nodesC << '\n';
        cout << "same," << ((nodesA == nodesB && nodesB == nodesC) ? 1 : 0) << '\n';
    } else {
        cout << "n = " << n << "，解的个数 = " << totA << '\n';
        cout << "① 逐个比      走了 " << nodesA << " 个节点\n";
        cout << "③ 标记数组    走了 " << nodesB << " 个节点\n";
        cout << "④ 位运算      走了 " << nodesC << " 个节点\n";
        cout << (nodesA == nodesB && nodesB == nodesC
                 ? "⇒ ★★ 三种写法走的是同一棵树，节点数一个都不差 —— 差的只是每个节点多贵\n"
                 : "⇒ 节点数不一样（那说明剪枝真的不同）\n");
    }
    return 0;
}

// 第 ③ 版（推荐写法）：三个标记数组，判合法从 O(行号) 变成 O(1)
//
// ★ 关键的一步只有一句话：**同一条对角线上的格子，有一个和是不变的**。
//
//     ↘ 方向（左上到右下）：行 − 列 相同  ⇒ 用 d2[r - c + n] 标记（加 n 是为了不出现负下标）
//     ↙ 方向（右上到左下）：行 + 列 相同  ⇒ 用 d1[r + c] 标记
//
// 于是「这一格能不能放」= 查三个布尔值，不用回头看前面的皇后。
// ⚠ 而这一版必须**老老实实撤销**（第 4 章那一课）：标记是全局的，进去改了，出来要还原。
//
// ★★ 注意它和第 ② 版**搜索的是同一棵树** —— 走过的节点数一个都不差（正文第 ④ 步实测）。
//   快的不是「少走了路」，是「每一步便宜了」。

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

int n;
int pos_[20];
bool col[20], d1[40], d2[40];
long long total_ = 0;
int printed = 0;

void dfs(int r) {
    if (r > n) {
        total_++;
        if (printed < 3) {
            printed++;
            for (int i = 1; i <= n; i++)
                cout << pos_[i] << (i == n ? '\n' : ' ');
        }
        return;
    }
    for (int c = 1; c <= n; c++) {
        if (col[c] || d1[r + c] || d2[r - c + n]) continue;
        col[c] = d1[r + c] = d2[r - c + n] = true;   // 进入
        pos_[r] = c;
        dfs(r + 1);
        col[c] = d1[r + c] = d2[r - c + n] = false;  // ⚠ 撤销
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    dfs(1);
    cout << total_ << '\n';
    return 0;
}