Visualize the N-Queens problem with step-by-step backtracking. Watch queen placements, conflicts and undo steps while exploring the search tree.
Recursion stack
Empty — nothing placed yet.
Columns tried
Press Start to search a 6 × 6 board.
How it works: N-Queens (Backtracking)
Step by step
- Placed queen
- Square being tried
- Rejected square, or a queen being lifted
- Squares the placed queens attack
Press Start or Step: the step the animation is on lights up below.
- 1
Try the next column in this row
Pick the next untried square in the current row. The faint wash on the board marks squares already attacked by the queens placed so far.
for col in range(n): - 2
Attacked → reject the square
A placed queen shares this square's column or a diagonal. The red line points to it. Rejecting now saves exploring every board that builds on this square.
if col in cols or row-col in diag or row+col in anti: continue - 3
Safe → place a queen and recurse
Commit the queen, record its column and diagonals, and move to the next row. The recursion stack grows by one.
queens.append(col); place(row + 1) - 4
Dead end → undo and try the next column
Every square in the next row was attacked, so this queen can't be part of a solution here. Remove it, restoring exactly the state from before, and carry on with the next column.
queens.pop() # backtrack - 5
Every row has a queen → solution
Reaching row N means N non-attacking queens are on the board. Record it, and either stop or keep backtracking to find the rest.
if row == n: solutions.append(queens.copy())
Place N queens on an N×N board so that no two share a row, column or diagonal. There are far too many arrangements to try them all, but most can be ruled out early: once two queens attack each other, nothing placed afterwards can fix it.
Backtracking builds the answer one row at a time. In each row, try the columns left to right and skip any square a placed queen attacks. On a safe square, place a queen and move to the next row. If a row has no safe square left, the choice before it was wrong. Lift the previous queen and try its next column.
That try → recurse → undo loop is a depth-first search over partial boards. The recursion stack is the list of queens placed so far, and every undo is a pop.
Spot it in an interview
- “Generate all” or “find any” arrangements that satisfy constraints: permutations, subsets, combinations, Sudoku, word search, and partitioning a string into palindromes.
- When a partial answer can be shown invalid early. That pruning is what makes backtracking far faster than brute force.
- When the answer is a sequence of choices you can make one at a time and also take back.
Each row has at most one queen, so there are at most N choices, then N − 1, and so on. Pruning cuts far deeper in practice: finding all 92 solutions to 8 queens takes 2,056 placements, against 8! = 40,320 arrangements, and the first solution takes only 113. Space is the recursion depth plus the column and diagonal sets.