L14. N-Queens | Leetcode Hard | Backtracking

1. Overview and Problem Statement

The N-Queens problem is a classic algorithmic challenge in Data Structures and Algorithms (DSA) that asks us to place $N$ non-attacking queens on an $N \times N$ chessboard. In chess, a queen can attack any piece sharing the same row, column, or diagonal.

To solve this problem successfully, we must satisfy three fundamental constraints:

1. Row Constraint: Every row must contain exactly one queen.
2. Column Constraint: Every column must contain exactly one queen.
3. Diagonal Constraint: No two queens can threaten each other along any diagonal (neither upper-left, lower-left, nor principal diagonals).

The primary objective is to generate all valid distinct board configurations that satisfy these conditions for an $N \times N$ chessboard.

2. Core Mental Model and Rules of Placement

Real-Life Analogy & Intuition

Think of placing queens on a grid as seating $N$ high-profile diplomats at a summit where no two diplomats can be in line of sight of one another horizontally, vertically, or diagonally. If diplomat #3 is placed in a specific seat, it immediately blocks out entire rows, columns, and diagonal corridors, restricting where subsequent diplomats can sit.

Chessboard (4 x 4) Initial State
 .  .  .  .
 .  .  .  .
 .  .  .  .
 .  .  .  .

The Three Attacking Directions for a Queen

When placing a queen at coordinate $(row, col)$, we must ensure it does not attack or get attacked by any previously placed queen in:

• Horizontal/Vertical lines: Handled naturally by placing exactly one queen per column and iterating row-by-row or column-by-column.
• Upper-Left / Lower-Left Diagonals: Checked dynamically to ensure no prior queen occupies the diagonal path.

3. Naive vs. Better Approach

• Naive Approach (Brute Force): Try every possible combination of placing $N$ queens across $N^2$ squares ($N^{N}$ possibilities), then validate each configuration. This is wildly inefficient and results in exponential time complexity that times out instantly for larger $N$.
• Better Approach (Backtracking): Place queens column by column (or row by row). As soon as an invalid placement is detected (a conflict with a previous queen), abandon that path immediately, backtrack by removing the last placed queen, and try the next available row in that column. This prunes invalid branches early in the search tree.

4. Step-by-Step Evolution of Backtracking Walkthrough

Let's trace how backtracking operates on a $4 \times 4$ board when filling column by column:

1. Column 0: Place a queen at row 0. Valid. Move to Column 1.
2. Column 1: Try row 0 (conflict with Col 0 row 0). Try row 1 (diagonal conflict). Try row 2 (Valid!). Move to Column 2.
3. Column 2: Try row 0 (conflict). Try row 1 (conflict). Try row 2 (conflict). Try row 3 (conflict). No valid spot in Column 2!
4. Backtrack: Step back to Column 1, remove the queen at row 2, and try the next available row (row 3).
5. Repeat this systematic exploration until all valid configurations are discovered and stored.

5. Algorithmic Implementation (C++)

Below is the clean C++ implementation demonstrating the recursive backtracking structure for solving N-Queens.

#include <vector>
#include <string>

class Solution {
private:
    void solve(int col, vector<string>& board, vector<vector<string>>& ans, 
               vector<int>& leftRow, vector<int>& lowerDiagonal, vector<int>& upperDiagonal, int n) {
        // Base Case: If all columns are filled, we found a valid configuration
        if (col == n) {
            ans.push_back(board);
            return;
        }

        // Try placing a queen in every row of the current column
        for (int row = 0; row < n; row++) {
            // Check if the position is safe using O(1) lookup arrays
            if (leftRow[row] == 0 && lowerDiagonal[row + col] == 0 && upperDiagonal[n - 1 + col - row] == 0) {
                // Place the queen
                board[row][col] = 'Q';
                leftRow[row] = 1;
                lowerDiagonal[row + col] = 1;
                upperDiagonal[n - 1 + col - row] = 1;

                // Recurse to the next column
                solve(col + 1, board, ans, leftRow, lowerDiagonal, upperDiagonal, n);

                // Backtrack: Remove the queen and reset markers
                board[row][col] = '.';
                leftRow[row] = 0;
                lowerDiagonal[row + col] = 0;
                upperDiagonal[n - 1 + col - row] = 0;
            }
        }
    }

public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> ans;
        vector<string> board(n, string(n, '.'));
        
        // Optimization lookup vectors for O(1) safety checks
        vector<int> leftRow(n, 0);
        vector<int> lowerDiagonal(2 * n - 1, 0);
        vector<int> upperDiagonal(2 * n - 1, 0);

        solve(0, board, ans, leftRow, lowerDiagonal, upperDiagonal, n);
        return ans;
    }
};

6. Optimizing Diagonal Checks in $O(1)$ Time

Checking diagonals by scanning upwards and sidewards takes $O(N)$ time per placement, slowing down the algorithm. We can optimize safety checks to $O(1)$ constant time using mathematical formulas for diagonals:

Why these formulas work:

• Lower Diagonal (row + col): Every square along a specific bottom-left to top-right diagonal shares an identical sum of its row and column indices.
• Upper Diagonal (n - 1 + col - row): Every square along a specific top-left to bottom-right diagonal shares a constant difference between row and column indices (offset by n - 1 to prevent negative array indices).

7. Complete Flow Walkthrough

8. Real-World Practical Pitfalls & Edge Cases

• Index Out of Bounds: When calculating upper diagonal indices (n - 1 + col - row), failing to add the offset n - 1 will result in negative indices and segmentation faults.
• Forgetting to Reset State (Backtracking Failure): If you forget to set markers back to 0 and revert 'Q' to '.' after the recursive call returns, subsequent valid paths will be blocked incorrectly.
• Board Initialization: Ensure the board is properly initialized with dimensions $N \times N$ filled with periods (.), rather than uninitialized memory.

9. Summary and Key Takeaways

• Backtracking Paradigm: The N-Queens problem is solved efficiently by building solutions incrementally and abandoning dead ends immediately.
• Constraint Propagation: Enforcing one queen per column drastically reduces the search space compared to unconstrained grid searches.
• $O(1)$ Optimization: Utilizing hash vectors for rows and diagonals (row, row + col, n - 1 + col - row) eliminates the need for nested scanning loops.
• State Reversal: Backtracking requires meticulous cleanup—every action taken when moving forward (placing a queen, marking lookup arrays) must be undone when retreating.
• Complexity: The time complexity is $O(N!)$ in the worst-case search space, significantly pruned by backtracking, with space complexity bounded by $O(N^2)$ for board storage and recursion stack.