N-Queens
hardDiagonals are just r−c and r+c, so the safety test is three hash lookups. Rejecting a placement at row 2 kills every branch beneath it - which is where all the performance lives.
O(n!)Space O(n)Saved in this browser - no sign-up, nothing sent anywhere.
How n-queens works
Place n queens on an n×n board so that no two share a row, column, or diagonal. Since two queens in one row always attack, the search only decides which column each row uses - modelling alone shrinks the space from C(n², n) placements to nⁿ. From there the solver runs the standard skeleton row by row: choose a column, explore the next row, undo the placement on the way back.
The safety test needs no board scan. Queens on the same ↘ diagonal share r − c, and queens on the same ↙ diagonal share r + c, so three hash sets - cols, diag1, diag2 - answer the question in three O(1) lookups. When the test fails, the solver skips that column without recursing, and everything that would have grown beneath the placement is never built.
Pruning is where all the performance lives, and the visualizer proves it with numbers. The unconstrained space for the default 6×6 board is 6⁶ = 46,656 placements; the engine finds the first solution after visiting just 32 nodes, because rejecting a placement at row 2 kills every branch beneath it. Reach for backtracking whenever a partial answer can be proven wrong early - the earlier the conflict, the bigger the subtree it removes.
Step by step
- Run n = 4. Row 0 tries column 0 first - the board is empty, so the queen is placed and the solver recurses into row 1.
- Row 1 rejects columns 0 and 1 - shared column, shared ↘ diagonal - and places its queen at column 2.
- Row 2 finds all four columns attacked. The branch is dead, so the row 1 queen is removed and re-placed at column 3.
- Row 2 now takes column 1, but row 3 is again fully attacked. The solver unwinds every placement and restarts row 0 at column 1.
- From (0, 1) the search falls straight through: row 1 takes column 3, row 2 takes column 0, row 3 takes column 2.
- All four rows are filled - the first solution, columns 1, 3, 0, 2, found after visiting 9 nodes out of 256 unconstrained placements.
Complexity
| Worst case time | O(n!) |
|---|---|
| Space | O(n) |
One queen per row cuts the space to nⁿ before pruning; pruning does the rest.
Reference implementation
Python
def solve_n_queens(n):
cols, diag1, diag2 = set(), set(), set()
board, out = [], []
def backtrack(row):
if row == n:
out.append(board[:])
return
for col in range(n):
if col in cols or (row - col) in diag1 or (row + col) in diag2:
continue # prune - O(1) check
cols.add(col); diag1.add(row - col); diag2.add(row + col)
board.append(col) # choose
backtrack(row + 1) # explore
board.pop() # undo
cols.discard(col)
diag1.discard(row - col)
diag2.discard(row + col)
backtrack(0)
return outJavaScript
function solveNQueens(n) {
const cols = new Set(), d1 = new Set(), d2 = new Set();
const board = [], out = [];
(function backtrack(row) {
if (row === n) { out.push([...board]); return; }
for (let col = 0; col < n; col++) {
if (cols.has(col) || d1.has(row - col) || d2.has(row + col)) continue;
cols.add(col); d1.add(row - col); d2.add(row + col);
board.push(col);
backtrack(row + 1);
board.pop();
cols.delete(col); d1.delete(row - col); d2.delete(row + col);
}
})(0);
return out;
}Worth noticing
One queen per row is a constraint, not a discovery
Two queens in the same row always attack, so the search only ever needs to decide which column each row uses. That reduces the space from C(n², n) to nⁿ before a single check runs - the biggest win here comes from modelling, not from code.
Diagonals are just r−c and r+c
Cells on the same ↘ diagonal share r−c; on the same ↙ diagonal they share r+c. Three hash sets turn the safety test into three O(1) lookups instead of scanning the board.
Undo is what makes it backtracking
The state is mutated on the way down and restored on the way up, so one board is reused for the entire search instead of copying it at every node. Forget the undo and the search silently explores a corrupted state.
Pruning early is worth more than pruning well
Rejecting a placement at row 2 kills every branch beneath it. Switch the pruning toggle off and compare the node counts - the constraint check is doing almost all the work.
Common pitfalls
- Undoing only part of the state. A removed queen must leave cols, diag1, and diag2 as well as the board - clearing two of the three sets silently corrupts every later branch.
- Copying the board at every recursive call instead of mutating one shared board. The whole point of choose-explore-undo is that a single board serves the entire search.
- Testing rows for conflicts. One queen per row is built into the recursion itself, so a row check is wasted work - only columns and the two diagonals can clash.
- Mixing up the diagonals. The ↘ diagonal is r − c and the ↙ diagonal is r + c; using the same expression for both lets attacking queens through.
- Recording a solution without copying, as in out.append(board). The board keeps mutating afterwards, so every recorded solution ends up pointing at the same final state.
Where it is used
- The standard benchmark for constraint-satisfaction solvers - new pruning and ordering heuristics are routinely demonstrated on N-Queens first.
- Scheduling and assignment problems where resources conflict in pairs, such as placing exams or radio frequencies so neighbours never clash.
- The canonical hard backtracking interview question - LeetCode 51 and 52 ask for all solutions and for the count.
- A teaching model for SAT encodings - each cell becomes a boolean variable and each attack rule becomes a clause.
Frequently asked questions
What is the time and space complexity of N-Queens?
Worst-case time is O(n!) - row 0 has n choices and the column rule leaves each later row fewer than the one above. Space is O(n): one column per row, three conflict sets, and a recursion stack n deep. The bound is still exponential, but pruning cuts the 6×6 board from 46,656 raw placements to 32 visited nodes.
What is the difference between backtracking and brute force?
Brute force builds every complete candidate and tests it afterwards; backtracking tests partial candidates and abandons a prefix the moment it breaks a constraint. Rejecting column 2 at row 1 means no board starting that way is ever built. Same worst case, wildly different practice - 46,656 raw placements versus 32 visited nodes on the default board.
How many solutions does the 8-queens problem have?
92, of which 12 are distinct once rotations and reflections are folded together. Set the board size to 8 and switch off stop-at-first: the engine finds all 92 after visiting 2,057 nodes - out of 8⁸ = 16,777,216 unconstrained placements.
Why are the diagonals r minus c and r plus c?
Moving one step down-right adds 1 to the row and 1 to the column, so r − c stays constant along every ↘ diagonal; moving down-left keeps r + c constant instead. Each placed queen therefore claims one value in each set, and the safety test becomes three hash lookups.