N-Queens - Video Solutions

Problem Overview: Place n queens on an n x n chessboard so that no two queens attack each other. Queens attack along rows, columns, and diagonals. The task is to return every valid board configuration.

The key constraint: each row must contain exactly one queen, and no two queens can share the same column or diagonal. That naturally leads to exploring placements row by row while rejecting invalid states early.

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

This is the classic solution used in most interviews. Build the board one row at a time and try placing a queen in every column of the current row. Before placing, check whether the column or either diagonal already contains a queen. Efficient implementations track conflicts using three structures: a columns set, a diag1 set for row - col, and a diag2 set for row + col. If a position is safe, place the queen, recurse to the next row, and backtrack afterward. The search space is roughly factorial because each row branches across remaining valid columns, but pruning invalid placements early keeps it manageable.

Backtracking works well because the constraints are local and easy to validate in O(1). You only store the column index for each row and generate the board representation when a valid solution is found. This approach directly demonstrates recursive state exploration, a core technique in backtracking problems.

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

This version replaces sets or arrays with bit masks to track used columns and diagonals. Three integers represent occupied positions: cols, diag1, and diag2. For each row, compute available positions using bit operations like ~(cols | diag1 | diag2). Extract the lowest available bit with pos & -pos, place a queen there, and recurse with updated masks. Diagonal masks shift left or right when moving to the next row.

Bit operations make conflict checks extremely fast and reduce memory overhead. This approach is common in competitive programming and scales better for larger n. It also demonstrates how arrays and bitsets can represent board states compactly. Many optimized solutions for constraint problems use similar masking techniques, which are often categorized under backtracking with pruning.

Recommended for interviews: Start with row-wise backtracking. Interviewers expect this solution because it clearly shows constraint checking, recursion, and pruning. Once that works, mention the bitmask optimization to demonstrate deeper understanding of performance improvements. The optimized version doesn't change the asymptotic complexity (~O(N!)) but significantly reduces constant factors.