---
title: "N-Queens"
description: "Place N queens with no two attacking — backtrack the moment a column dies."
source: https://vizlearn.app/algorithms/backtracking/n-queens
---

# N-Queens

N-Queens is a backtracking problem: place one queen in every row of an `n x n` chessboard so that no two queens share a column or diagonal. The solver tries columns left to right, abandons a candidate at the first conflict, and undoes earlier choices when a row has nowhere legal to go.

Think of each placed queen signing three ledgers. One records its column, one records `row - col`, and one records `row + col`. A new queen may sit only if all three signatures are absent. When a branch fails, you erase the departing queen from every ledger. Miss one erasure and the paperwork starts rejecting queens that do not exist.

## How N-Queens backtracking works

The solver assigns rows in order. That decision quietly removes one entire constraint: two queens can never share a row because the recursion places exactly one queen before calling `search(row + 1)`. The remaining attacks have compact keys:

- Queens in the same column have the same `col`.
- Queens on a `\` diagonal have the same `row - col`.
- Queens on a `/` diagonal have the same `row + col`.

Three sets make each safety check O(1). If any key is already present, the candidate is rejected without changing the board. A safe candidate is appended to `queens`, then its three keys enter the sets. If the recursive call succeeds, that result propagates outward. If it fails, the solver pops the queen and removes all three keys before trying the next column.

That last sentence is the backtracking invariant: after a failed recursive call, the caller must see exactly the state it had before making the choice. Backtracking is not vague "going backward." It is a precise rollback.

This shape turns up wherever constraints can be checked incrementally and rolled back cheaply: Sudoku, timetable and resource assignment, backtracking regex engines, and the decision search inside SAT or constraint-programming solvers. The state looks different, but the contract is the same: choose, reserve, recurse, then restore every reservation on failure.

This lesson stops at the first solution. It does not enumerate every solution, use symmetry to skip mirrored boards, or pack constraints into bitmasks. Those are useful extensions, but they are different machines.

## N-Queens step by step

The default board is `n = 4`, with columns tried in order `0, 1, 2, 3`.

1. `search(0)` tries `(0, 0)`. All three ledgers are empty, so the queen is placed and the solver descends to row 1.
2. Row 1 rejects `(1, 0)` because column 0 is occupied. It rejects `(1, 1)` because both squares have `row - col = 0`. Candidate `(1, 2)` is safe, so the prefix is now `[0, 2]`.
3. Row 2 has no legal column. Column 0 is occupied; column 1 meets the queen at `(1, 2)` on a `/` diagonal; column 2 is occupied; column 3 meets `(1, 2)` on a `\` diagonal. The row returns false.
4. The solver removes `(1, 2)` and releases its column and diagonal keys. Row 1 resumes at column 3, places `(1, 3)`, and descends again.
5. Row 2 places `(2, 1)`, but row 3 then rejects all four columns. The solver undoes `(2, 1)`. Row 2 has no later legal choice, so it returns false; row 1 then undoes `(1, 3)` as well.
6. Row 1 is exhausted. The first queen at `(0, 0)` is removed. This is the important rollback: the board and all three ledgers are empty again before row 0 tries its next column.
7. Row 0 places `(0, 1)`. Row 1 rejects columns 0, 1, and 2, then places `(1, 3)`. Row 2 places `(2, 0)`. Row 3 rejects columns 0 and 1, then places `(3, 2)`.
8. The recursion reaches row 4, which is the base case. The returned column vector is `[1, 3, 0, 2]`: row 0 uses column 1, row 1 uses column 3, row 2 uses column 0, and row 3 uses column 2.

The run checks 26 candidate squares, makes 8 provisional placements, and performs 4 backtracks. Its 18 immediate conflict rejections prevent 114 raw suffix assignments from ever being generated. For comparison, an unconstrained four-row board has `4^4 = 256` complete row assignments, while enforcing unique columns leaves `4! = 24` complete permutations. Those are different units: 26 counts candidate nodes visited; 256 and 24 count complete boards.

On the board, one red conflict line names the queen that blocks the current candidate. An `X` means the candidate failed a key check immediately and never owned a queen. A rollback ring means the candidate was legal, the solver searched below it, and that subtree later failed. The right panel draws the future row choices behind a rejection, so `4 x 4 = 16` means sixteen descendant row assignments never come into existence.

## Time and space complexity

| Measure | Bound | Reason |
|---|---:|---|
| Candidate space with unique columns | O(N!) | One queen per row and unique columns reduce the raw `N^N` row assignments to permutations; diagonal checks prune many prefixes earlier. |
| Time complexity of this code | O(N × N!) upper bound | Every surviving prefix still scans all N columns of the next row. |
| Candidate safety check | O(1) expected | Three hash-set membership tests replace scanning every placed queen. |
| Auxiliary space | O(N) | At most N queens, N recursive calls, and O(N) occupied keys live at once. |

The exact work depends heavily on column order. With the same left-to-right code, `n = 4` backtracks four times before its first solution, while `n = 5` reaches `[0, 2, 4, 1, 3]` without a single undo. A larger board is not automatically a harder first-solution trace.

Use this direct set-backed search when you need one valid assignment and the search tree is small enough to tolerate. Asking for every solution removes the successful early return: record each board and keep searching, which means paying for the remaining viable tree. For larger N, bitmasks and symmetry cuts are the usual next steps; for richer scheduling or allocation rules, a constraint-programming or SAT solver is often the honest tool.

## Edge cases

- `n = 1` has the immediate solution `[0]`.
- `n = 2` and `n = 3` have no solution. The solver must exhaust row 0 and return `None` in Python or `null` in JavaScript with every set empty.
- The canvas accepts `1 <= n <= 5` so individual candidates remain readable. That is a visualization limit, not an algorithmic limit.
- Changing the column order can change both the first solution and the number of backtracks, even though the set of valid boards is unchanged.
- This implementation returns one solution. To collect all solutions, a successful base case must record a copy and continue searching instead of returning immediately.

## Common mistakes

- **Undoing only the board.** Popping `queens` without deleting the column and both diagonal keys leaves stale constraints. Valid branches then look illegal.
- **Using the wrong diagonal formulas.** `row - col` is constant on `\` diagonals; `row + col` is constant on `/` diagonals. Swapping the names is harmless if the checks stay consistent, but mixing the formulas between add and remove corrupts the state.
- **Returning false after the first failed child.** A failed column means "try the next column," not "this row is impossible." The false return belongs after the loop.
- **Mutating on rejection.** A conflicting candidate never enters `queens` or any set. Rejecting and then "cleaning up" creates extra state transitions and invites mismatched deletes.
- **Forgetting what the result vector means.** The index is the row and the stored value is the column. `[1, 3, 0, 2]` is a board, not a sequence of queen IDs.