nqueens.cpp

// nqueens.cpp
// -----------------------------------------------------------------
// N-Queens：回溯法入門經典
//   1. 基本回溯：三個布林陣列 O(1) 衝突檢查
//   2. 位元運算加速版（competitive programming 風格）
//   3. 輸出一組具體解（棋盤圖）
//
// Compile: g++ -std=c++17 -O2 -Wall -Wextra -o nqueens nqueens.cpp
// -----------------------------------------------------------------
#include <iostream>
#include <vector>
#include <chrono>

using namespace std;

// ---------- 1. 基本回溯（教學版） ----------
class NQueensBasic {
    int n;
    vector<bool> col, d1, d2;    // 直行、主對角(r+c)、副對角(r-c+n-1)
    vector<int> pos;             // pos[row] = 該列皇后放的行
public:
    long long solutions = 0;
    long long nodes = 0;
    vector<int> firstSolution;

    void run(int n_) {
        n = n_;
        solutions = nodes = 0;
        col.assign(n, false);
        d1.assign(2 * n - 1, false);
        d2.assign(2 * n - 1, false);
        pos.assign(n, -1);
        firstSolution.clear();
        dfs(0);
    }
private:
    void dfs(int row) {
        ++nodes;
        if (row == n) {
            ++solutions;
            if (firstSolution.empty()) firstSolution = pos;
            return;
        }
        for (int c = 0; c < n; ++c) {
            if (col[c] || d1[row + c] || d2[row - c + n - 1]) continue; // 剪枝
            col[c] = d1[row + c] = d2[row - c + n - 1] = true;
            pos[row] = c;
            dfs(row + 1);
            col[c] = d1[row + c] = d2[row - c + n - 1] = false;
        }
    }
};

// ---------- 2. 位元運算版（每個位元 = 一行是否被攻擊） ----------
class NQueensBitmask {
    int n, full;
public:
    long long solutions = 0;
    long long count(int n_) {
        n = n_;
        full = (1 << n) - 1;
        solutions = 0;
        dfs(0, 0, 0);
        return solutions;
    }
private:
    void dfs(int cols, int diag1, int diag2) {
        if (cols == full) { ++solutions; return; }
        // 可放位置 = 不被三種攻擊覆蓋的位元
        int avail = full & ~(cols | diag1 | diag2);
        while (avail) {
            int bit = avail & (-avail);        // 取最低位的 1
            avail ^= bit;
            dfs(cols | bit, (diag1 | bit) << 1, (diag2 | bit) >> 1);
        }
    }
};

static void printBoard(const vector<int>& sol) {
    int n = (int)sol.size();
    for (int r = 0; r < n; ++r) {
        for (int c = 0; c < n; ++c)
            cout << (sol[r] == c ? " Q" : " .");
        cout << "\n";
    }
}

int main() {
    // ---- 範例 1：n=4 到 n=8 的解數 ----
    cout << "=== Example 1: solution counts ===\n";
    NQueensBasic nb;
    for (int n = 4; n <= 8; ++n) {
        nb.run(n);
        cout << "n=" << n << " -> " << nb.solutions
             << " solutions (search nodes=" << nb.nodes << ")\n";
    }
    cout << "\n";

    // ---- 範例 2：印出 n=8 的第一組解 ----
    cout << "=== Example 2: one solution for n=8 ===\n";
    nb.run(8);
    printBoard(nb.firstSolution);
    cout << "\n";

    // ---- 範例 3：剪枝的威力——比較節點數與天真枚舉 ----
    cout << "=== Example 3: pruning power ===\n";
    nb.run(8);
    cout << "n=8: naive enumeration = 8^8 = 16,777,216 placements\n";
    cout << "     backtracking visited only " << nb.nodes << " nodes\n\n";

    // ---- 範例 4：位元版 vs 基本版效能 ----
    cout << "=== Example 4: basic vs bitmask timing ===\n";
    NQueensBitmask nq;
    for (int n : {10, 12, 14}) {
        auto t0 = chrono::steady_clock::now();
        nb.run(n);
        auto t1 = chrono::steady_clock::now();
        long long c2 = nq.count(n);
        auto t2 = chrono::steady_clock::now();
        cout << "n=" << n << " solutions=" << nb.solutions
             << " | basic "
             << chrono::duration<double, milli>(t1 - t0).count() << " ms"
             << " | bitmask "
             << chrono::duration<double, milli>(t2 - t1).count() << " ms"
             << " | agree=" << (nb.solutions == c2 ? "yes" : "NO!") << "\n";
    }
    return 0;
}