The N-Queens problem is a classic algorithmic problem that consists of placing N chess queens on an N×N chessboard such that no two queens threaten each other. This means that no two queens can be on the same row, column, or diagonal.

Algorithm Overview

The problem can be solved using a backtracking algorithm. The general idea is to place queens one by one in different columns, starting from the leftmost column. When placing a queen in a column, we check for the safety of that position, ensuring that no other queen is placed in the same row or diagonal.

Steps to Solve the Problem

1. Start from the leftmost column.
2. Try all rows in the current column. For each row, check if it is safe to place the queen.
3. If it is safe, mark the position and move to the next column.
4. If placing the queen leads to a solution, return true. If not, backtrack and remove the queen from that position.
5. Continue this process until all queens are placed or all possibilities are exhausted.

C++ Implementation

#include <iostream>
#include <vector>

using namespace std;

/**
 * Class to solve the N-Queens problem.
 */
class NQueens {
private:
    int N; // Size of the chessboard
    vector<vector<string>> solutions; // Store solutions

    /**
     * Checks if it is safe to place a queen at board[row][col].
     */
    bool isSafe(vector<string> &board, int row, int col) {
        // Check this row on left side
        for (int i = 0; i < col; i++)
            if (board[row][i] == 'Q') return false;

        // Check upper diagonal on left side
        for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)
            if (board[i][j] == 'Q') return false;

        // Check lower diagonal on left side
        for (int i = row, j = col; j >= 0 && i < N; i++, j--)
            if (board[i][j] == 'Q') return false;

        return true;
    }

    /**
     * Solves the N-Queens problem using backtracking.
     */
    void solveNQueensUtil(vector<string> &board, int col) {
        if (col == N) {
            solutions.push_back(board);
            return;
        }

        for (int i = 0; i < N; i++) {
            if (isSafe(board, i, col)) {
                board[i][col] = 'Q'; // Place queen
                solveNQueensUtil(board, col + 1); // Recur
                board[i][col] = '.'; // Backtrack
            }
        }
    }

public:
    /**
     * Constructor to initialize the N-Queens problem.
     */
    NQueens(int n) : N(n) {}

    /**
     * Solves the N-Queens problem and returns all solutions.
     */
    vector<vector<string>> solve() {
        vector<string> board(N, string(N, '.'));
        solveNQueensUtil(board, 0);
        return solutions;
    }
};

int main() {
    int N;
    cout << "Enter the number of queens: ";
    cin >> N;

    NQueens nQueens(N);
    vector<vector<string>> solutions = nQueens.solve();

    cout << "Total solutions found: " << solutions.size() << endl;
    for (const auto &solution : solutions) {
        for (const auto &row : solution) {
            cout << row << endl;
        }
        cout << endl;
    }

    return 0;
}

Conclusion

This C++ program implements a backtracking solution to the N-Queens problem, effectively demonstrating the algorithm’s structure and logic. The solution stores all possible arrangements of queens on the board without any conflicts, providing a comprehensive method to tackle this classic problem.