C++ Program: N-Queens Problem Solution (Backtracking)

N-Queens Problem: วาง N Queens บนหมากรุก N×N ให้ไม่มี Queen ตัวใดโจมตีกันได้ (ไม่อยู่ Row, Column, หรือ Diagonal เดียวกัน)

Backtracking Algorithm

1. วาง Queen ทีละ Column (หรือ Row)
2. ตรวจสอบความปลอดภัย: Row, Upper Diagonal, Lower Diagonal
3. ถ้าปลอดภัย → วาง Queen, Recurse Column ถัดไป
4. ถ้าไม่ปลอดภัยหรือ Recursive ล้มเหลว → Backtrack (ถอด Queen)
5. ถ้าวางครบ N Columns → Found Solution

Optimization: Bitmasks (O(1) Validation)

แทน Array 2D ใช้ 3 Bitmasks:

• columns: Column ที่มี Queen แล้ว
• diag1: Main Diagonal (Row + Col = Constant)
• diag2: Anti Diagonal (Row - Col + N - 1 = Constant)

โค้ด C++ (Bitmask Version - Fast)

#include <iostream>
#include <vector>
#include <cstdint>
using namespace std;

class NQueens {
    int n;
    uint64_t columns = 0, diag1 = 0, diag2 = 0;
    vector solution;
    vector> allSolutions;
    uint64_t allColumnsMask;
    
public:
    NQueens(int n_) : n(n_), allColumnsMask((n == 64) ? ~0ULL : (1ULL << n) - 1) {}
    
    void solve() {
        backtrack(0);
    }
    
    void backtrack(int row) {
        if (row == n) {
            allSolutions.push_back(solution);
            return;
        }
        
        // Available positions: ~(columns | diag1 | diag2) & allColumnsMask
        uint64_t available = ~(columns | diag1 | diag2) & allColumnsMask;
        
        while (available) {
            // Get rightmost 1-bit (LSB)
            uint64_t bit = available & -available;
            available -= bit; // Remove this bit
            
            int col = __builtin_ctzll(bit); // Count trailing zeros = column index
            
            // Place Queen
            solution.push_back(col);
            columns |= bit;
            diag1 |= (bit << 1);
            diag2 |= (bit >> 1);
            
            backtrack(row + 1);
            
            // Backtrack
            columns ^= bit;
            diag1 ^= (bit << 1);
            diag2 ^= (bit >> 1);
            solution.pop_back();
        }
    }
    
    void printSolutions(int maxPrint = 10) {
        cout << "Total solutions: " << allSolutions.size() << "\n\n";
        for (int i = 0; i < min(maxPrint, (int)allSolutions.size()); i++) {
            cout << "Solution " << (i+1) << ":\n";
            printBoard(allSolutions[i]);
            cout << "\n";
        }
    }
    
    void printBoard(const vector& sol) {
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                cout << (sol[r] == c ? "Q " : ". ");
            }
            cout << "\n";
        }
    }
    
    size_t count() const { return allSolutions.size(); }
};

int main() {
    int n;
    cout << "Enter N (1-14 recommended): ";
    cin >> n;
    
    if (n < 1 || n > 14) {
        cout << "N too large for enumeration. Use 1-14.\n";
        return 1;
    }
    
    NQueens solver(n);
    solver.solve();
    solver.printSolutions();
    
    return 0;
}

ผลลัพธ์สำหรับ N=4

Total solutions: 2

Solution 1:
. Q . .
. . . Q
Q . . .
. . Q .

Solution 2:
. . Q .
Q . . .
. . . Q
. Q . .

Number of Solutions (Known Sequence)

Complexity

• Time: O(N!) Worst Case, แต่ Bitmask + Pruning เร็วมาก (N=14 ~ วินาที)
• Space: O(N) Recursion + O(Solutions × N) Storage

Variations

• Count Only: ไม่เก็บ Solution, ใช้ Symmetry Breaking เร็วขึ้น 8x
• One Solution: หยุดตอนเจอ Solution แรก
• N-Queens Completion: บาง Queen วางไว้ล่วงหน้า
• Toroidal Board: Wrap-around Diagonals

การแก้ N=8 แบบ Classic (Array-based)

bool isSafe(const vector& board, int row, int col) {
    for (int i = 0; i < row; i++) {
        if (board[i] == col) return false;                    // Same column
        if (abs(board[i] - col) == row - i) return false;     // Diagonal
    }
    return true;
}

void solveClassic(vector& board, int row, vector>& solutions) {
    int n = board.size();
    if (row == n) { solutions.push_back(board); return; }
    
    for (int col = 0; col < n; col++) {
        if (isSafe(board, row, col)) {
            board[row] = col;
            solveClassic(board, row + 1, solutions);
            board[row] = -1;
        }
    }
}