← Back to DSA Animator
N-Queens LC #51 Hard Backtracking · Constraint Sets
Problem

Place n queens on an n×n chessboard such that no two queens attack each other. Return all distinct solutions. 'Q' = queen, '.' = empty.

Example 1
Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: 2 distinct solutions for the 4-queens problem.
Example 2
Input: n = 1
Output: [["Q"]]
Constraints: 1 ≤ n ≤ 9
Try Examples
Custom:
Approach
Row-by-Row + Three Constraint Sets
Place one queen per row. Use sets: cols (same column), diag1 (row-col, ↘), diag2 (row+col, ↗). O(1) set lookups give huge pruning power.
Board
 Solutions: 0
Constraint Sets
cols
{}
diag1 (r-c)
{}
diag2 (r+c)
{}
Variables
row
0
queens[]
—
solutions
0
Step Logic
Press ▶ Play or Next Step to begin.
✅
Ready
0 / 0
Select an example above and press Play.
Algorithm
1
Place one queen per row (iterate row by row)
2
Three constraint sets: cols, diag1(row-col), diag2(row+col) — O(1) lookup each
3
Base: row==n → all queens placed, record solution
4
Backtrack: remove queen, delete from all three sets
Time
O(n!)
Space
O(n)
Why Backtracking Works

Row-by-row placement ensures one queen per row. cols set checks columns, diag1(row-col) checks ↘ diagonals, diag2(row+col) checks ↗ diagonals. Three O(1) set lookups per cell give massive pruning. Only valid columns are explored at each row.