N-Queens - Video Solutions

Problem Overview: Place n queens on an n x n chessboard so that no two queens attack each other. A queen attacks horizontally, vertically, and diagonally, so every placement must avoid conflicts in the same column or diagonal.

Approach 1: Backtracking with Row-wise Construction (Time: O(N!), Space: O(N) to O(N²))

This approach builds the board one row at a time using backtracking. For each row, try placing a queen in every column and check whether that column or either diagonal already contains a queen. Validity checks typically use three structures: a column set, a major diagonal set (row - col), and a minor diagonal set (row + col). If a position is safe, place the queen, recurse to the next row, and backtrack if the placement leads to no valid continuation.

The key insight: once you place exactly one queen per row, you eliminate horizontal conflicts entirely. The algorithm only needs to track columns and diagonals. The recursion explores a decision tree with branching factor up to N, leading to worst‑case time complexity of about O(N!). Space complexity is O(N) for recursion and tracking structures, or O(N²) if you store the entire board explicitly. This is the standard solution used in most explanations of the classic N‑Queens puzzle.

Backtracking works well here because the constraints prune the search tree early. As soon as a queen conflicts with an existing one, the branch stops expanding. Problems involving placement and constraint satisfaction often use arrays to represent board state combined with recursive exploration.

Approach 2: Bit Manipulation Optimization (Time: O(N!), Space: O(N))

This version replaces sets or arrays with integer bitmasks to represent occupied columns and diagonals. Each bit in an integer corresponds to a column. Three masks track constraints: cols, diag1 (major diagonal), and diag2 (minor diagonal). At each row, compute available positions using bit operations such as ~(cols | diag1 | diag2), then extract the lowest set bit to place a queen.

After placing a queen, update masks using shifts: (diag1 | pos) << 1 and (diag2 | pos) >> 1. Bit operations make conflict checks constant time and eliminate hash structures. The theoretical complexity remains O(N!), but the constant factors are significantly smaller. This technique is common in optimized competitive programming solutions and scales better for larger n.

Recommended for interviews: Interviewers typically expect the row‑wise backtracking solution. It clearly demonstrates recursive search, pruning logic, and constraint tracking. The bitmask version shows deeper optimization skills and strong understanding of state compression. Starting with classic backtracking and then discussing bitmask improvements signals strong problem‑solving depth.