DSA AnimatorDSA animations
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.

How to solve N-Queens

LeetCode 51 · Hard · Backtracking · Pattern: Backtracking on a Board

Why the obvious approach is slow

Trying every way to place n queens on n squared cells is enormous. There is exactly one queen per row, so place them row by row.

The key idea

For the current row, try each column. Skip a column if a queen above shares its column or one of its diagonals. Place the queen, recurse to the next row, then remove it.

Remember

One queen per row, and check column and both diagonals. Row minus column and row plus column identify the diagonals.

Run the animation above on your own input, or watch the 1:32 video explanation of N-Queens with a dry run and Java code.

More Backtracking problems