DSA problem
N-Queens
The N-Queens puzzle asks you to place n queens on an n x n chessboard such that no two queens attack each other. Two queens attack each other if they share the same row, the same column, or the same diagonal. Return all distinct solutions; each solution is a list of n strings of length n where 'Q' marks a queen and '.' marks an empty square.
This is the canonical exact-cover backtracking problem. The naive search over all C(n^2, n) queen placements is hopeless — we need the structure of the problem. Two observations cut the work dramatically: (1) each row contains exactly one queen, so we can fix the row index and only decide its column; and (2) we can detect column and diagonal conflicts in O(1) using three sets.
For an n x n board, the two diagonal families are uniquely identified by the affine combinations r - c (anti-diagonal index, ranges -(n-1)..(n-1)) and r + c (main diagonal index, ranges 0..2n-2). So we maintain three boolean sets: cols, diag1 = r - c, and diag2 = r + c. Placing a queen at (r, c) adds these three keys; removing it on backtrack pops them.
The recursive routine backtrack(row) tries every column at row row; for each conflict-free column it places the queen, recurses to row + 1, then removes the queen. When row == n we have placed all n queens with no conflicts and build the board representation by translating each row's column choice into a string of '.' characters with a single 'Q'. Total time is roughly O(n!) thanks to the cut at each conflict; space is O(n) for the recursion and bookkeeping sets.
Examples
n = 4[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]n = 1[["Q"]]n = 2[]Constraints
- 1 <= n <= 9
- Each row must contain exactly one queen.
- No two queens may share a column.
- No two queens may share an anti-diagonal (constant r - c).
- No two queens may share a main diagonal (constant r + c).
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.