Giải bài toán N-Queen (N hậu) trong C++

Bài toán N-Queen: Đặt N quân hậu lên bàn cờ N×N sao cho không có 2 quân nào ăn được nhau (không cùng hàng, cột, đường chéo).

Thuật toán: Backtracking (Quay lui)

Đặt quân hậu cột bởi cột (hoặc hàng bởi hàng). Tại mỗi cột, thử từng hàng. Kiểm tra an toàn: không có quân nào cùng hàng, đường chéo chính, đường chéo phụ.

Kiểm tra an toàn O(1) với mảng đánh dấu

Thay vì quét bàn cờ, dùng 3 mảng boolean:

• rows[r]: hàng r đã có hậu.
• diag1[r+c]: đường chéo chính (r+c cố định).
• diag2[r-c+N-1]: đường chéo phụ (r-c cố định, dịch +N-1 để không âm).

Chương trình C++ tối ưu

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

class NQueens {
    int N;
    vector cols;           // cols[r] = c: hậu tại hàng r, cột c
    vector rows, d1, d2;  // Đánh dấu hàng, chéo chính, chéo phụ
    vector> solutions;
    
    bool isSafe(int r, int c) const {
        return !rows[r] && !d1[r+c] && !d2[r-c+N-1];
    }
    
    void place(int r, int c) {
        cols[r] = c;
        rows[r] = d1[r+c] = d2[r-c+N-1] = true;
    }
    
    void remove(int r, int c) {
        cols[r] = -1;
        rows[r] = d1[r+c] = d2[r-c+N-1] = false;
    }
    
    void solve(int col) {
        if (col == N) {
            solutions.push_back(cols);
            return;
        }
        for (int row = 0; row < N; ++row) {
            if (isSafe(row, col)) {
                place(row, col);
                solve(col + 1);
                remove(row, col);
            }
        }
    }
    
    void printBoard(const vector& sol) const {
        for (int r = 0; r < N; ++r) {
            for (int c = 0; c < N; ++c)
                cout << (sol[r] == c ? "Q " : ". ");
            cout << '\n';
        }
        cout << '\n';
    }

public:
    NQueens(int n) : N(n), cols(n, -1), rows(n), d1(2*n), d2(2*n) {}
    
    void findAll() { solve(0); }
    
    void printAll() const {
        cout << "Tong so giai phap N=" << N << ": " << solutions.size() << "\n\n";
        for (size_t i = 0; i < solutions.size(); ++i) {
            cout << "Giai phap " << i+1 << ":\n";
            printBoard(solutions[i]);
        }
    }
    
    void printOne() const {
        if (solutions.empty()) { cout << "Khong co giai phap\n"; return; }
        printBoard(solutions[0]);
    }
};

int main() {
    int N;
    cout << "Nhap N (kich thuoc ban co): ";
    cin >> N;
    
    NQueens nq(N);
    nq.findAll();
    nq.printOne(); // In 1 giải pháp đầu tiên
    // nq.printAll(); // Bỏ comment để in tất cả (N=8 có 92 nghiệm)
    return 0;
}

Kết quả N=4

Nhap N (kich thuoc ban co): 4
Tong so giai phap N=4: 2

Giai phap 1:
. Q . .
. . . Q
Q . . .
. . Q .

Số nghiệm cho các N

Tối ưu hóa nâng cao

• Bitmask (Bitwise): Dùng 3 integer (bitset) thay vì vector — cực nhanh, N ≤ 32/64. Xem thuật toán Bitwise N-Queens.
• Đối xứng: Chỉ duyệt nửa đầu hàng đầu tiên, nhân đôi kết quả (trừ trường hợp đối xứng).
• Song song hóa: Phân chia nhánh đầu tiên cho các thread.
• Constraint Programming / SAT Solver: Dùng OR-Tools, Z3 cho N lớn.

Bitmask version (N ≤ 32, siêu nhanh)

void solveBit(int col, int rows, int d1, int d2) {
    if (col == N) { count++; return; }
    int available = ~(rows | d1 | d2) & ((1<>1);
    }
}

N-Queen là bài toán kinh điển dạy tư duy backtracking, pruning, và tối ưu bitmask — kỹ năng cốt lõi cho thi đấu lập trình và AI (constraint satisfaction).