8 Queens Problem in C++ - Backtracking Solution

Q: How do I compile the C++ 8 queens program?

Use g++ -std=c++11 -O2 -o nqueens nqueens.cpp on Linux/macOS or with MinGW on Windows. Then run ./nqueens (Linux/macOS) or nqueens.exe (Windows). MSVC users can use cl /EHsc /O2 nqueens.cpp .

Setup & Prerequisites

C++ is an excellent choice for solving the 8 queens problem when performance is critical. The language's zero-cost abstractions, stack-allocated arrays, and bitwise operators make it possible to write a solver that runs in microseconds for n=8 and milliseconds for n=15.

You will need:

A C++11 or later compiler: g++ (GCC), clang++, or MSVC on Windows
Standard headers: <iostream>, <vector>, <cmath>

The algorithm is identical to the backtracking approach described in the algorithm guide. We represent the board as a vector<int> where board[row] = col.

C++ Implementation

The following complete C++ program finds all 92 solutions to the 8 queens problem using recursive backtracking:

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int solutionCount = 0;

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

void printBoard(const vector<int>& board, int n) {
    cout << "Solution " << solutionCount << ":\n";
    for (int row = 0; row < n; row++) {
        for (int col = 0; col < n; col++) {
            cout << (board[row] == col ? "Q " : ". ");
        }
        cout << "\n";
    }
    cout << "\n";
}

void solve(vector<int>& board, int row, int n) {
    if (row == n) {
        solutionCount++;
        printBoard(board, n);
        return;
    }
    for (int col = 0; col < n; col++) {
        if (isSafe(board, row, col)) {
            board[row] = col;
            solve(board, row + 1, n);
            board[row] = -1; // backtrack
        }
    }
}

int main() {
    int n = 8;
    vector<int> board(n, -1);
    solve(board, 0, n);
    cout << "Total solutions for " << n << "-Queens: " << solutionCount << "\n";
    return 0;
}

Bitwise Optimization Version

The standard version above runs the isSafe check in O(row) time. For large n, a bitwise approach using three integer bitmasks is dramatically faster — O(1) per candidate check. This is the same technique described in the backtracking guide, implemented in C++:

#include <iostream>
using namespace std;

int count = 0;

// cols: occupied columns
// d1: occupied main diagonals (row - col)
// d2: occupied anti-diagonals (row + col)
void solve(int row, int n, int cols, int d1, int d2) {
    if (row == n) {
        count++;
        return;
    }
    int fullMask = (1 << n) - 1;
    int available = fullMask & ~(cols | d1 | d2);
    while (available) {
        int bit = available & -available;  // isolate lowest set bit
        available &= available - 1;        // clear lowest set bit
        solve(row + 1, n,
              cols | bit,
              (d1 | bit) << 1,
              (d2 | bit) >> 1);
    }
}

int main() {
    int n = 8;
    solve(0, n, 0, 0, 0);
    cout << "Total solutions: " << count << "\n"; // 92
    return 0;
}

Compilation & Running

To compile and run the standard version with g++:

# Standard solution
g++ -std=c++11 -O2 -o nqueens nqueens.cpp
./nqueens

# Bitwise solution (save as nqueens_bit.cpp)
g++ -std=c++11 -O2 -o nqueens_bit nqueens_bit.cpp
./nqueens_bit

On Windows with MinGW:

g++ -std=c++11 -O2 -o nqueens.exe nqueens.cpp
nqueens.exe

With MSVC (Visual Studio Developer Command Prompt):

cl /EHsc /O2 nqueens.cpp
nqueens.exe

Expected output for n=8: 92 total solutions. The bitwise version will typically be 5–20× faster than the vector version for large n due to reduced memory access and elimination of the inner loop in isSafe. Try the interactive puzzle to visualize any of the 92 solutions.

Frequently Asked Questions

How do I compile the C++ 8 queens program?

Use g++ -std=c++11 -O2 -o nqueens nqueens.cpp on Linux/macOS or with MinGW on Windows. Then run ./nqueens (Linux/macOS) or nqueens.exe (Windows). MSVC users can use cl /EHsc /O2 nqueens.cpp.

How much faster is the C++ bitwise version compared to the standard version?

Typically 5–20× faster for n≥10. For n=8 both run under 1ms, so the difference is negligible. The advantage grows with board size because bitwise operations eliminate the O(row) inner loop in isSafe, reducing it to a constant-time bitmask check.

Can I solve N queens for n > 20 in C++?

The bitwise version works for n up to 30 (using 32-bit integers) or n up to 62 (using 64-bit integers with long long). For n=20 there are 39,029,188 solutions. A single-threaded C++ bitwise solver can enumerate them in roughly 30 seconds. Parallel approaches using OpenMP or std::thread can reduce this significantly.

8 Queens Problem in C++ - Backtracking Solution

Table of Contents

Setup & Prerequisites

C++ Implementation

Bitwise Optimization Version

Compilation & Running

Frequently Asked Questions

Related Pages

8 Queens in Python

8 Queens in Java

8 Queens Backtracking Guide

N Queens Algorithm Overview

Interactive Puzzle