N-Queens

N-Queens

What is this problem about?

The N-Queens problem asks you to place n queens on an n×n chessboard such that no two queens threaten each other — no two queens share the same row, column, or diagonal. Return all distinct solutions. This N-Queens coding problem is the canonical backtracking problem and a cornerstone of algorithm interview preparation.

Why is this asked in interviews?

Apple, Microsoft, Meta, Amazon, Google, Bloomberg, Goldman Sachs, and dozens of other companies ask this as the definitive test of backtracking ability. It demonstrates constraint propagation, state-space search, and pruning — skills that transfer to scheduling, constraint satisfaction, and combinatorial optimization. The array and backtracking interview pattern is exemplified perfectly here.

Algorithmic pattern used

Backtracking with column/diagonal tracking. Place queens one row at a time. For each row, try all columns. A placement is valid if the column, left diagonal, and right diagonal are all unoccupied. Use sets to track occupied columns (cols), left diagonals (row-col), and right diagonals (row+col). Recurse to the next row. When all n rows are filled, record the solution. Backtrack by removing the queen and clearing the sets.

Example explanation

n=4. Row 0: try col 0 → col 0, diag (-0,+0). Row 1: col 0 blocked (same col), col 1 blocked (row-col=0), col 2: row-col=1-2=-1 (ok), row+col=1+2=3 (ok). Place at (1,2). Row 2: continue placing... eventually find valid placements. Total solutions for n=4 = 2.

Common mistakes candidates make

• Checking row conflicts (unnecessary — placing one queen per row automatically avoids this).
• Not tracking diagonals separately (left diagonal: row-col, right diagonal: row+col).
• Backtracking incorrectly — not removing the queen from all three sets before trying next column.
• Constructing the board incorrectly (place 'Q' at chosen column, '.' everywhere else).

Interview preparation tip

N-Queens is the must-know backtracking problem. Memorize the three constraint sets (cols, left diag, right diag) and the one-queen-per-row structure. The diagonal encoding — row-col uniquely identifies each left diagonal, row+col each right diagonal — is elegant and reusable in any constraint problem on a grid. After mastering this, practice N-Queens II (count solutions without building boards) and "N-Queens with forbidden cells" as follow-ups. Backtracking fluency built here applies to Sudoku solver, word search, and combination sum problems.