C++ Program for N Queens Problem with Output and Explanation

A C++ program for the N Queens problem uses backtracking to place queens safely on an n x n board by checking rows, columns, and diagonals, as shown in this code snippet: bool solveNQueens(int n) { /* backtracking logic */ }.

Examples

Input4

OutputSolution 1: . Q . . . . . Q Q . . . . . Q . Solution 2: . . Q . Q . . . . . . Q . Q . .

Input1

OutputSolution 1: Q

Input2

OutputNo solutions exist for n=2

How to Think About It

To solve the N Queens problem, think of placing one queen per row. For each row, try placing a queen in each column and check if it is safe by ensuring no other queen attacks it vertically or diagonally. If safe, move to the next row. If stuck, backtrack and try a different position.

Algorithm

1

Start with the first row.

2

Try placing a queen in each column of the current row.

3

Check if the queen placement is safe (no other queens in the same column or diagonals).

4

If safe, move to the next row and repeat.

5

If all queens are placed, print the board as a solution.

6

If no column works in a row, backtrack to the previous row and try a different column.

Code

cpp

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

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

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

bool solveNQueensUtil(vector<int>& queens, int row) {
    int n = queens.size();
    if (row == n) {
        printBoard(queens);
        return true;
    }
    bool found = false;
    for (int col = 0; col < n; ++col) {
        if (isSafe(queens, row, col)) {
            queens[row] = col;
            found = solveNQueensUtil(queens, row + 1) || found;
        }
    }
    return found;
}

int main() {
    int n;
    cout << "Enter number of queens: ";
    cin >> n;
    vector<int> queens(n, -1);
    if (!solveNQueensUtil(queens, 0)) {
        cout << "No solutions exist for n=" << n << "\n";
    }
    return 0;
}

Output

Enter number of queens: 4
Solution 1:
. Q . . 
. . . Q 
Q . . . 
. . Q . 

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

Dry Run

Let's trace the program for n=4 through the code.

1

Start with row 0

Try placing queen in columns 0 to 3. Place at column 1 (safe).

2

Move to row 1

Try columns 0 to 3. Column 3 is safe, place queen there.

3

Move to row 2

Try columns 0 to 3. Column 0 is safe, place queen there.

4

Move to row 3

Try columns 0 to 3. Column 2 is safe, place queen there.

5

All queens placed

Print the board as one solution.

Row	Queen Column
0	1
1	3
2	0
3	2

Why This Works

Step 1: Check safety with isSafe

The isSafe function ensures no two queens share the same column or diagonal by comparing positions of previously placed queens.

Step 2: Backtracking tries all options

If a queen cannot be placed in any column of a row, the algorithm backtracks to the previous row to try a different column.

Step 3: Print all solutions

When all queens are placed safely, the board is printed showing one valid solution.

Alternative Approaches

Bitmask Optimization

cpp

#include <iostream>
using namespace std;

int count = 0;
void solve(int n, int row, int cols, int diags1, int diags2) {
    if (row == n) {
        count++;
        return;
    }
    int available = ((1 << n) - 1) & ~(cols | diags1 | diags2);
    while (available) {
        int pos = available & -available;
        available -= pos;
        solve(n, row + 1, cols | pos, (diags1 | pos) << 1, (diags2 | pos) >> 1);
    }
}

int main() {
    int n;
    cout << "Enter number of queens: ";
    cin >> n;
    solve(n, 0, 0, 0, 0);
    cout << "Total solutions: " << count << "\n";
    return 0;
}

Uses bit operations for faster checks and counts solutions but does not print boards.

Iterative Backtracking

cpp

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

int main() {
    int n;
    cout << "Enter number of queens: ";
    cin >> n;
    vector<int> queens(n, -1);
    int row = 0, col = 0, solutions = 0;
    while (row >= 0) {
        while (col < n) {
            bool safe = true;
            for (int i = 0; i < row; ++i) {
                if (queens[i] == col || abs(queens[i] - col) == row - i) {
                    safe = false;
                    break;
                }
            }
            if (safe) {
                queens[row] = col;
                col = 0;
                break;
            } else {
                ++col;
            }
        }
        if (queens[row] == -1) {
            --row;
            if (row >= 0) col = queens[row] + 1;
        } else if (row == n - 1) {
            ++solutions;
            queens[row] = -1;
            col = n;
        } else {
            ++row;
        }
    }
    cout << "Total solutions: " << solutions << "\n";
    return 0;
}

Uses loops instead of recursion to find solutions, harder to read but avoids stack overhead.

Complexity: O(n!) time, O(n) space

Time Complexity

The algorithm tries to place queens in each row and column, pruning invalid positions early, but worst case explores factorial possibilities.

Space Complexity

Uses an array of size n to store queen positions, plus recursion stack up to depth n.

Which Approach is Fastest?

Bitmask optimization is fastest for counting solutions, while backtracking with arrays is clearer and prints boards.

Approach	Time	Space	Best For
Backtracking with arrays	O(n!)	O(n)	Printing all solutions, clarity
Bitmask Optimization	O(n!) but faster in practice	O(n)	Counting solutions efficiently
Iterative Backtracking	O(n!)	O(n)	Avoiding recursion overhead