回溯与状态恢复：N 皇后

// N 皇后 —— 暴力：先把所有摆法生成出来，再一个个检查
//
// 输入：n
// 输出：n×n 棋盘上放 n 个皇后、互不攻击的方案数
//
// 皇后互相攻击的条件：同行、同列、同一条对角线。
//
// 第一步观察（这一步很关键，不然连暴力都写不出来）：
//   n 个皇后放进 n 行，每行必须恰好一个 —— 两个皇后同行就直接完蛋了。
//   所以一种摆法 = 「第 0 行放第几列，第 1 行放第几列，……」这样一个序列。
//   又因为不能同列，这个序列必须是 0..n-1 的一个**排列**。
//
// 于是暴力就成了：枚举 0..n-1 的全排列（第 3 章刚学的），
// 每生成一个完整排列，就检查一遍对角线冲突。
//
// 这份代码思路完全正确，n = 8 秒出。但它有个致命的浪费，正文第 5 步会把它揪出来：
// **它必须把 n 个皇后全部摆完，才肯回头检查第 1、2 个皇后是不是早就打起来了。**

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

int main() {
    int n;
    if (!(cin >> n)) return 0;
    if (n <= 0) { cout << 0 << "\n"; return 0; }

    vector<int> col(n);
    for (int i = 0; i < n; i++) col[i] = i;    // col[r] = 第 r 行的皇后放在第几列

    long long ans = 0;
    do {
        // 排列本身已经保证了「不同行、不同列」，只剩对角线要查
        bool ok = true;
        for (int r1 = 0; r1 < n && ok; r1++)
            for (int r2 = r1 + 1; r2 < n && ok; r2++)
                if (abs(r1 - r2) == abs(col[r1] - col[r2]))    // 行差 == 列差，就是在同一条对角线上
                    ok = false;
        if (ok) ans++;
    } while (next_permutation(col.begin(), col.end()));

    cout << ans << "\n";
    return 0;
}

// 剪枝到底省了多少 —— 把两种做法的工作量并排数出来
//
// 输入：n（建议 10 ~ 12）
// 输出：一张表，对每个 k <= n 列出
//         k!                 暴力要检查的完整摆法数
//         回溯访问的节点数     加了剪枝之后真正走过的地方
//         两者的倍数
//         解的个数
//
// 这份代码不解题，它只是把「剪枝值多少钱」变成具体数字。
// 注意看倍数那一列：它不是稳定的几倍，而是**随着 n 越来越大**。
// 这说明剪枝省掉的不是一个常数，而是改变了增长的速度本身。

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

int n;
vector<bool> col, d1, d2;
long long solutions = 0, nodes = 0;

void dfs(int r) {
    nodes++;
    if (r == n) { solutions++; return; }
    for (int c = 0; c < n; c++) {
        if (col[c] || d1[r - c + n - 1] || d2[r + c]) continue;
        col[c] = d1[r - c + n - 1] = d2[r + c] = true;
        dfs(r + 1);
        col[c] = d1[r - c + n - 1] = d2[r + c] = false;
    }
}

int main() {
    int maxN;
    if (!(cin >> maxN)) return 0;
    if (maxN < 1 || maxN > 13) { cout << "请输入 1 到 13 之间的 n（再大这份统计自己就跑慢了）\n"; return 0; }

    cout << "  n        n! (暴力)     回溯节点数      省了几倍     解的个数\n";
    cout << "---   --------------   ------------   ----------   ----------\n";

    long long fact = 1;
    for (int k = 1; k <= maxN; k++) {
        fact *= k;

        n = k;
        col.assign(k, false);
        d1.assign(2 * k, false);
        d2.assign(2 * k, false);
        solutions = 0;
        nodes = 0;
        dfs(0);

        cout << setw(3) << k
             << setw(17) << fact
             << setw(15) << nodes
             << setw(13) << fixed << setprecision(1) << (double)fact / (double)nodes
             << setw(13) << solutions << "\n";
    }
    return 0;
}

// N 皇后 —— 回溯，但冲突判断用最朴素的办法：和前面每一个皇后比一遍
//
// 输入：n
// 输出：方案数（和 brute.cpp / fast.cpp 完全一样）
//
// 这份为什么存在：正文第 7 步要先有它，才轮得到三个标记数组。
//
// 很多人把「回溯」和「三个标记数组」当成同一件事 —— 不是。
// **回溯是骨架，标记数组只是骨架里那句「冲突吗？」的一种写法。**
// 这份和 fast.cpp 的关系：
//   · 走的是同一棵树，访问的节点数一个不差（nodes.cpp 数出来的那一列对它同样成立）；
//   · 剪掉的是同一批枝；
//   · 答案逐字节相同（check:viz 里 n = 1..10 钉着这一条）。
// 唯一的差别是**判断一次冲突要花多少功夫**：这份要和已放的 r 个皇后逐个比，
// fast.cpp 只查三个数组。count.cpp 把这两个数并排数出来。
//
// ⚠ 所以「先写这份、跑通、再换成标记数组」是一条安全的路 ——
//    考场上一时想不起对角线的下标怎么算，这份照样是满分做法，只是常数大一点。

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

int n;
vector<int> pos;      // pos[r] = 第 r 行的皇后放在第几列（只有 0..r-1 这一段是有效的）
long long ans = 0;

// (r, c) 和已经放好的第 0..r-1 行的皇后冲突吗？
bool conflict(int r, int c) {
    for (int i = 0; i < r; i++) {
        if (pos[i] == c) return true;                    // 同列
        if (r - i == abs(c - pos[i])) return true;       // 同对角线：行差 == 列差
    }
    return false;
}

void dfs(int r) {
    if (r == n) { ans++; return; }                       // 出口：n 行全放满了

    for (int c = 0; c < n; c++) {
        if (conflict(r, c)) continue;                    // ★ 剪枝：和 fast.cpp 剪的是同一批枝

        pos[r] = c;                                      // 进入
        dfs(r + 1);                                      // 递归
        // 撤销：这一份什么都不用写 —— 因为 conflict() 只读 pos[0..r-1]，
        // 也就是「只看比自己早的行」。写在 pos[r] 上的那个数，兄弟分支下一轮就覆盖掉了，
        // 谁也看不见它。⇒ 需不需要撤销，取决于**别人会不会读到你留下的痕迹**。
        // fast.cpp 的三个标记数组是整块棋盘共用的，所以那边非撤不可。正文第 7 步讲这件事。
    }
}

int main() {
    if (!(cin >> n)) return 0;
    if (n <= 0) { cout << 0 << "\n"; return 0; }

    pos.assign(n, -1);

    dfs(0);
    cout << ans << "\n";
    return 0;
}

// N 皇后 —— 回溯 + 剪枝
//
// 输入：n
// 输出：方案数（和 brute.cpp 完全一样）
//
// 和暴力的差别只有一句话：**每放下一个皇后就立刻检查，一冲突就掉头。**
//
// 三段式（这一章要练成肌肉记忆的东西）：
//     col[c] = d1[...] = d2[...] = true;    // 进入：占用这一列和两条对角线
//     dfs(r + 1);                           // 递归：交给下一行
//     col[c] = d1[...] = d2[...] = false;   // 撤销：恢复现场，让兄弟分支能用
//
// 「撤销」为什么必须有：从 dfs(r+1) 回来之后，我们要在**同一行**试下一个列。
// 试下一个列之前，必须把上一次的占用全部还回去，否则棋盘上会残留一个不存在的皇后。
// 忘写撤销是初学回溯的头号错误 —— 而且它不报错，只是答案偷偷变小。
//
// 两条对角线的编号（想清楚这个就不用每次现推）：
//   ↘ 方向（左上到右下）：同一条上的格子 r - c 相同。加 n-1 是为了让下标非负 → r - c + n - 1
//   ↙ 方向（右上到左下）：同一条上的格子 r + c 相同 → r + c

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

int n;
vector<bool> col, d1, d2;   // 列 / ↘ 对角线 / ↙ 对角线 是否已经被占
long long ans = 0;

void dfs(int r) {
    if (r == n) { ans++; return; }          // 出口：n 行全放满了，凑出一个方案

    for (int c = 0; c < n; c++) {
        if (col[c] || d1[r - c + n - 1] || d2[r + c]) continue;   // ★ 剪枝：冲突就根本不往下走

        col[c] = d1[r - c + n - 1] = d2[r + c] = true;   // 进入
        dfs(r + 1);                                      // 递归
        col[c] = d1[r - c + n - 1] = d2[r + c] = false;  // 撤销
    }
}

int main() {
    if (!(cin >> n)) return 0;
    if (n <= 0) { cout << 0 << "\n"; return 0; }

    col.assign(n, false);
    d1.assign(2 * n, false);
    d2.assign(2 * n, false);

    dfs(0);
    cout << ans << "\n";
    return 0;
}

// 两种冲突判断，各要做多少次「基本操作」—— 换一把可复现的尺子
//
// 输入：n（1 ~ 13）
// 输出：一张表，对每个 k <= n 列出
//         试过的格子数       两种写法完全相同（它们走的是同一棵树）
//         逐个比较的次数     scan.cpp：每试一个格子，就和已放的皇后逐个比
//         查标记数组的次数   fast.cpp：每试一个格子，最多查 col / d1 / d2 三下
//         倍数
//
// 为什么用「次数」而不是秒表：秒数换台机器就变，次数不变 —— 这本书一贯的做法
//（第 21、36、38 章都是这么干的）。何况这两份程序都很快，秒表量到的大半是起进程的开销。
//
// ★ 这张表真正要说的是：**剪枝剪掉的枝一模一样** —— 所以「试过的格子数」只有一列，
//   两种写法共用。差别全在「每试一个格子要花多少功夫」上。
//
// 两边都按 C++ 的短路求值数，数出来才和真跑的一致：
//   逐个比较：一旦发现冲突就 return，后面的皇后不比了；
//   查标记数组：col[c] 为真就不查 d1，d1 为真就不查 d2。
//
// 顺带做了一件自检的事：两种判断对每一个格子给出的结论必须一模一样，
// 不一样就当场报错退出 —— 这份代码自己就是「新写法和老写法等价」的一个证人。

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

int n;
vector<int> pos;                 // 逐个比较那一份要用的
vector<bool> col, d1, d2;        // 三个标记数组那一份要用的
long long cells = 0, cmps = 0, looks = 0, solutions = 0;
bool disagreed = false;

void dfs(int r) {
    if (r == n) { solutions++; return; }

    for (int c = 0; c < n; c++) {
        cells++;

        // ① scan.cpp 的判断：和前面每一个皇后比（发现冲突就不比了）
        bool scanBad = false;
        for (int i = 0; i < r; i++) {
            cmps++;
            if (pos[i] == c || r - i == abs(c - pos[i])) { scanBad = true; break; }
        }

        // ② fast.cpp 的判断：查三个标记数组（短路，所以最少 1 次、最多 3 次）
        looks++;
        bool markBad = col[c];
        if (!markBad) { looks++; markBad = d1[r - c + n - 1]; }
        if (!markBad) { looks++; markBad = d2[r + c]; }

        if (scanBad != markBad) disagreed = true;        // 两种判断必须给同一个结论

        if (markBad) continue;

        pos[r] = c;
        col[c] = d1[r - c + n - 1] = d2[r + c] = true;
        dfs(r + 1);
        col[c] = d1[r - c + n - 1] = d2[r + c] = false;
    }
}

int main() {
    int maxN;
    if (!(cin >> maxN)) return 0;
    if (maxN < 1 || maxN > 13) { cout << "请输入 1 到 13 之间的 n（再大这份统计自己就跑慢了）\n"; return 0; }

    cout << "  n    试过的格子数   逐个比较：比了几次   查标记数组：查了几次       倍数\n";
    cout << "---   -------------   ------------------   --------------------   --------\n";

    for (int k = 1; k <= maxN; k++) {
        n = k;
        pos.assign(k, -1);
        col.assign(k, false);
        d1.assign(2 * k, false);
        d2.assign(2 * k, false);
        cells = cmps = looks = solutions = 0;
        dfs(0);

        cout << setw(3) << k
             << setw(16) << cells
             << setw(21) << cmps
             << setw(23) << looks
             << setw(11) << fixed << setprecision(2) << (double)cmps / (double)looks << "\n";
    }

    if (disagreed) cout << "\n✗ 两种判断给出了不同的结论 —— 这不该发生，去查代码\n";
    else           cout << "\n✓ 每一个格子上，两种判断给出的结论都一样\n";
    return 0;
}

// N 皇后 —— 把回溯的每一步打印出来
//
// 输入：n（用 4 或 5，再大就刷屏了）
// 输出：每一次「尝试 / 冲突 / 放下 / 撤销」，缩进表示当前在第几行
//
// 请特别盯住两种行：
//   ✗ 冲突      —— 这一步之后**整棵子树都没走**。这就是剪枝，省下来的全是白工。
//   ← 撤回      —— 从递归回来后把占用还回去。没有它，后面的兄弟分支会看到一个幻影皇后。
//
// 最后会打印统计：真正进入了多少个节点、剪掉了多少次。
// 把它和「暴力要检查 n! 种摆法」比一比，就知道剪枝到底值多少钱。

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

int n;
vector<bool> col, d1, d2;
vector<int> pos;                 // pos[r] = 第 r 行皇后所在的列
long long ans = 0, nodes = 0, cuts = 0;

void indent(int r) {
    for (int i = 0; i < r; i++) cout << "|   ";
}

void printBoard() {
    for (int r = 0; r < n; r++) {
        cout << "        ";
        for (int c = 0; c < n; c++) cout << (pos[r] == c ? "Q " : ". ");
        cout << "\n";
    }
}

void dfs(int r) {
    nodes++;
    if (r == n) {
        ans++;
        indent(r);
        cout << "★ 第 " << ans << " 个解！\n";
        printBoard();
        return;
    }

    for (int c = 0; c < n; c++) {
        indent(r);
        cout << "第 " << r << " 行试第 " << c << " 列：";

        if (col[c] || d1[r - c + n - 1] || d2[r + c]) {
            cuts++;
            cout << "✗ 冲突（";
            if (col[c]) cout << "列 " << c << " 已有皇后";
            else if (d1[r - c + n - 1]) cout << "↘ 对角线上已有皇后";
            else cout << "↙ 对角线上已有皇后";
            cout << "）—— 这一整片分支直接不看了\n";
            continue;                                   // ★ 剪枝
        }

        cout << "✓ 放下\n";
        col[c] = d1[r - c + n - 1] = d2[r + c] = true;   // 进入
        pos[r] = c;

        dfs(r + 1);                                      // 递归

        col[c] = d1[r - c + n - 1] = d2[r + c] = false;  // 撤销
        pos[r] = -1;
        indent(r);
        cout << "← 撤回第 " << r << " 行第 " << c << " 列的皇后，换下一列试\n";
    }
}

int main() {
    if (!(cin >> n)) return 0;
    if (n <= 0 || n > 6) { cout << "这份是用来看过程的，请输入 1 到 6 之间的 n\n"; return 0; }

    col.assign(n, false);
    d1.assign(2 * n, false);
    d2.assign(2 * n, false);
    pos.assign(n, -1);

    dfs(0);

    long long fact = 1;
    for (int i = 2; i <= n; i++) fact *= i;

    cout << "\n解的个数：" << ans << "\n";
    cout << "回溯真正进入的节点数：" << nodes << "\n";
    cout << "被剪掉的分支次数：" << cuts << "\n";
    cout << "而暴力要老老实实检查 " << n << "! = " << fact << " 种完整摆法。\n";
    return 0;
}

// N 皇后 —— 回溯 + 剪枝
//
// 输入：n
// 输出：方案数（和 brute.cpp 完全一样）
//
// 和暴力的差别只有一句话：**每放下一个皇后就立刻检查，一冲突就掉头。**
//
// 三段式（这一章要练成肌肉记忆的东西）：
//     col[c] = d1[...] = d2[...] = true;    // 进入：占用这一列和两条对角线
//     dfs(r + 1);                           // 递归：交给下一行
//     col[c] = d1[...] = d2[...] = false;   // 撤销：恢复现场，让兄弟分支能用
//
// 「撤销」为什么必须有：从 dfs(r+1) 回来之后，我们要在**同一行**试下一个列。
// 试下一个列之前，必须把上一次的占用全部还回去，否则棋盘上会残留一个不存在的皇后。
// 忘写撤销是初学回溯的头号错误 —— 而且它不报错，只是答案偷偷变小。
//
// 两条对角线的编号（想清楚这个就不用每次现推）：
//   ↘ 方向（左上到右下）：同一条上的格子 r - c 相同。加 n-1 是为了让下标非负 → r - c + n - 1
//   ↙ 方向（右上到左下）：同一条上的格子 r + c 相同 → r + c

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

int n;
vector<bool> col, d1, d2;   // 列 / ↘ 对角线 / ↙ 对角线 是否已经被占
long long ans = 0;

void dfs(int r) {
    if (r == n) { ans++; return; }          // 出口：n 行全放满了，凑出一个方案

    for (int c = 0; c < n; c++) {
        if (col[c] || d1[r - c + n - 1] || d2[r + c]) continue;   // ★ 剪枝：冲突就根本不往下走

        col[c] = d1[r - c + n - 1] = d2[r + c] = true;   // 进入
        dfs(r + 1);                                      // 递归
        col[c] = d1[r - c + n - 1] = d2[r + c] = false;  // 撤销
    }
}

int main() {
    if (!(cin >> n)) return 0;
    if (n <= 0) { cout << 0 << "\n"; return 0; }

    col.assign(n, false);
    d1.assign(2 * n, false);
    d2.assign(2 * n, false);

    dfs(0);
    cout << ans << "\n";
    return 0;
}