N Queens

#include <bits/stdc++.h> // Includes common standard libraries like iostream, vector.
using namespace std;     // Use the standard namespace.

// Helper function to add a found solution board configuration to the overall solutions.
// 'board': The current N x N board with queen placements (1 for queen, 0 for empty).
// 'sol': The vector of vectors, where each inner vector is a flattened solution board.
void addSolution(vector<vector<int>> board, vector<vector<int>> &sol) {
    vector<int> temp; // Temporary 1D vector to store the flattened board.
    // Iterate through each row of the 2D board.
    for(vector<int> row_vec : board) {
        // Iterate through each element (cell) in the current row.
        for(int cell_val : row_vec) {
            temp.push_back(cell_val); // Add cell value (0 or 1) to the 1D vector.
        }
    }
    sol.push_back(temp); // Add the flattened board configuration to the list of solutions.
}

// Function to check if placing a queen at (row, col) is safe.
// It checks the current row (to the left), and both upper-left and lower-left diagonals.
// 'row', 'col': Coordinates where we want to place a queen.
// 'board': The current state of the N x N chessboard. Passed by value, consider 'const &' for efficiency.
// 'n': The size of the board.
bool isSafe(int row, int col, vector<vector<int>> board, int n) {
    // Check for queen in the same row to the left.
    // We only need to check left because queens in columns > col are not yet placed.
    for(int j = col; j >= 0; j--) {
        if(board[row][j] == 1) { // If a queen is found in this row.
            return false;
        }
    }

    // Check for queen in the upper-left diagonal.
    // 'i' goes up (row decreases), 'j' goes left (column decreases).
    for(int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
        if(board[i][j] == 1) { // If a queen is found on this diagonal.
            return false;
        }
    }

    // Check for queen in the lower-left diagonal.
    // 'i' goes down (row increases), 'j' goes left (column decreases).
    for(int i = row, j = col; i < n && j >= 0; i++, j--) {
        if(board[i][j] == 1) { // If a queen is found on this diagonal.
            return false;
        }
    }

    return true; // No attacking queen found, so it's safe.
}

// Recursive function to solve the N-Queens problem using backtracking.
// 'col': The current column where we are trying to place a queen.
// 'solution': Stores all valid board configurations found.
// 'board': The current state of the board. Passed by reference to allow modification.
// 'n': The size of the board.
void solve(int col, vector<vector<int>> &solution, vector<vector<int>> &board, int n) {
    // Base Case: If all queens are placed (we have successfully placed a queen in column n-1).
    if(col == n) {
        addSolution(board, solution); // Add the current board configuration to solutions.
        return;                       // Backtrack to the previous column.
    }

    // Try placing a queen in each row of the current 'col'.
    for(int row = 0; row < n; row++) {
        // Check if placing a queen at (row, col) is safe.
        if(isSafe(row, col, board, n)) {
            // If safe, place the queen.
            board[row][col] = 1;

            // Recursive call: Try to place the next queen in the next column.
            solve(col + 1, solution, board, n);

            // Backtracking Step: After the recursive call returns (either found solution
            // or hit a dead end), unplace the queen. This allows exploring other rows
            // in the current 'col'.
            board[row][col] = 0;
        }
    }
}

// Main function to initiate the N-Queens problem solution.
// 'n': The size of the N x N chessboard.
// Returns a vector of vectors representing all possible N-Queens configurations.
vector<vector<int>> nQueens(int n) {
    vector<vector<int>> solution; // Stores all valid N-Queens solutions.
    // Initialize an N x N board with all 0s (empty cells).
    vector<vector<int>> board(n, vector<int>(n, 0));

    // Start the backtracking process from the first column (col = 0).
    solve(0, solution, board, n);
    return solution; // Return all found solutions.
}

int main() {
    int n;
    cout << "Enter the value of n : ";
    cin >> n;

    // Get all N-Queens solutions.
    vector<vector<int>> solutions = nQueens(n);
    int i = 0; // Counter for displaying configurations.

    // Print all found solutions.
    if (solutions.empty()) {
        cout << "\nNo possible configurations for n = " << n << endl;
    } else {
        for(vector<int> config : solutions) {
            cout << endl << "Possible Configuration [" << ++i << "] : ";
            for(int val : config) {
                cout << val << " "; // Print 0 or 1 for each cell.
            }
        }
        cout << endl; // Final newline for clean output.
    }

    return 0; // Indicate successful execution.
}

1. Problem Statement

Goal: Place N non-attacking queens on an N x N chessboard. A queen can attack horizontally, vertically, and diagonally.
Output: Find all distinct configurations of queens. Each configuration is represented as an N x N board where 1 indicates a queen and 0 indicates an empty cell.
Key Constraint: No two queens can share the same row, column, or diagonal.

2. Approach: Backtracking

Core Idea: The N-Queens problem is a classic example of how backtracking can be used. We try to place queens one column at a time. For each column, we iterate through all possible rows. If placing a queen at (row, col) is “safe” (doesn’t conflict with previously placed queens), we place it and recursively try to place the next queen in the next column. If a placement leads to no solution (or we cannot place a queen in a subsequent column), we “backtrack” by removing the queen and trying a different row.

3. Algorithm Steps

isSafe(row, col, board, n) Function:
- Checks if placing a queen at (row, col) is safe, given the queens already placed in columns 0 to col-1.
- Assumptions: Since we place queens column by column from left to right, we only need to check:
  - Same Row: Check cells to the left in the current row.
  - Upper Left Diagonal: Check cells diagonally up-left.
  - Lower Left Diagonal: Check cells diagonally down-left.
- The current code passes board by value (vector<vector<int>> board), which causes a full copy of the board for each isSafe call, leading to performance issues for larger N. It’s better to pass it by const & or, even better, optimize checks using auxiliary arrays (see “Optimizations” below).
solve(col, solution, board, n) (Recursive Backtracking Function):
- Parameters:
  - col: The current column we are trying to place a queen in.
  - solution: vector<vector<int>> to store all valid board configurations.
  - board: The current N x N chessboard state (passed by reference so changes are reflected).
  - n: Size of the board.
- Base Case: If col == n:
  - This means we have successfully placed a queen in every column (from 0 to n-1).
  - A valid configuration is found. Add the current board to solution using addSolution and return.
- Recursive Step:
  - Iterate through each row from 0 to n-1 in the current col.
  - For each row:
    - Check Safety: Call isSafe(row, col, board, n).
    - If Safe:
      - Make a Move: Place a queen: board[row][col] = 1.
      - Recurse: Call solve(col + 1, solution, board, n) to try placing the next queen in the next column.
      - Backtrack: After the recursive call returns (meaning all possibilities from this placement have been explored), undo the move: board[row][col] = 0. This allows trying other rows in the current column.
addSolution(board, sol) Function:
- This helper converts the N x N board (2D vector) into a flattened 1D vector<int> (e.g., [0,0,1,0, 1,0,0,0, ...] for an 8x8 board) and adds it to the sol (all solutions) vector.
nQueens(int n) Function:
- Initializes an empty solution vector.
- Initializes an empty N x N board with all 0s.
- Calls the recursive solve function starting from col = 0.
- Returns the solution vector.

4. Optimizations for `isSafe` (Important for Performance)

The isSafe function as written has O(N) complexity per call (due to three loops), and it makes O(N) copies of the board if passed by value. This makes the overall complexity very high.

A better way to check safety is to use three boolean arrays/vectors:

rowCheck[N]: rowCheck[r] is true if a queen is in row r.
upperDiagonalCheck[2*N - 1]: upperDiagonalCheck[r + c] is true if a queen is on the upper diagonal r + c.
lowerDiagonalCheck[2*N - 1]: lowerDiagonalCheck[n - 1 + r - c] is true if a queen is on the lower diagonal n - 1 + r - c.

Using these arrays, isSafe becomes O(1). Update them when placing/removing a queen.

5. Complexity Analysis

Let N be the size of the chessboard.
Time Complexity: O(N!)
- In the worst case (unoptimized isSafe): Each solve call iterates N times for rows. Inside, isSafe takes O(N). This gives a rough upper bound of O(N * N!) or even worse with pass-by-value.
- With optimized isSafe (using boolean arrays for O(1) checks): The solve function essentially explores N branches at each level. The number of leaf nodes (solutions) is part of N!. The complexity is roughly O(N!). O(N^2 * N!) if board copying is included in addSolution and isSafe not optimized. The actual number of recursive calls is related to the number of nodes in the implicit state-space tree.
- The addSolution function copies an N x N board, which takes O(N^2) time per solution found. If S is the number of solutions, this adds O(S * N^2) to the total.
Space Complexity: O(N^2)
- board: O(N^2).
- Recursion stack depth: O(N) (for N recursive calls).
- solution: O(S * N^2) where S is the number of solutions. This can be large (exponential with N).
- Optimized isSafe would add O(N) space for the three boolean arrays.

6. Key Concepts

Backtracking: Incremental construction of solutions; pruning branches that cannot lead to a solution.
Recursion: The problem has optimal substructure and overlapping subproblems, making recursion a natural fit.
State Space Tree: The implicit tree representing all possible queen placements. Backtracking prunes branches of this tree.