Backtracking · LC #51
N-Queens
Place queens one row at a time using three sets to track occupied columns and diagonals. Backtrack when a row has no safe column.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Place `n` queens on an `n×n` chessboard so no two queens attack each other. Return all distinct solutions.
Sample I/O
Input: n=4 Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] Input: n=1 Output: [["Q"]]
Intuition
How to Think About It
Intuition
By placing exactly one queen per row, we reduce the problem to choosing a safe column for each row. Three sets compactly track all attacks: column conflicts, top-left-diagonal conflicts (row-col constant), and top-right-diagonal conflicts (row+col constant).
Core Concept
bt(row): if row==n, build and record board. For col in 0..n-1: if col in cols OR row-col in diag1 OR row+col in diag2 skip. Add to all three sets, recurse row+1, remove from all three sets.
When to use
Constraint satisfaction problems with mutual exclusion; any "place n items without conflict" problem; classic backtracking interview question.
When NOT to use
n > ~15 (solution count explodes); when you only need the count not the boards (N-Queens II - LC 52 uses bitmask DP).
Key Insights
What to Know Cold
- Three sets (cols, diag1=row-col, diag2=row+col) give O(1) conflict checking.
- diag1 = row-col is constant along any top-left-to-bottom-right diagonal.
- diag2 = row+col is constant along any top-right-to-bottom-left diagonal.
- One queen per row is forced - no need to try multiple placements per row.
- Bitmask version replaces sets with integers for O(1) bitwise ops and smaller constant.
1 example
Worked Examples
N-Queens for n=4
Find all valid placements of 4 queens on 4x4 board.
Row-by-row backtracking with column+diagonal conflict tracking.
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
N-Queens is the canonical backtracking problem; mastering it demonstrates deep understanding of constraint propagation and pruning.