N-Queens, traced one call at a time

Call backtrack(r) places the queen for row r. It tries each column, skips any square already attacked (checked in O(1) with three sets), and recurses to the next row. When a row has no safe square, the call returns and the row above moves its queen.

CALL
1 / 1

Code

The highlighted line runs next. The pill shows the live values in the running call.

Recursion tree

Labels list queens' columns by row · hover a solution in res to find it

not called yet running now paused, waiting on a child call solution (saved) finished, led to a solution dead end, no solution below

Call stack

Top frame runs; the rest are paused

Board

Hover a square to see its r − c and r + c

attacked lines what each set already blocks

♛queen attacked below safe in this row tried, attacked

res

Keyboard: ← → step, Space play or pause. n = 2 and n = 3 have no solutions, which makes them good for watching every branch dead-end. n = 4 has 2 solutions and n = 5 has 10.