N-Queens Backtracking Pseudocode: A Comprehensive Explanation

The N-Queens problem asks us to place $N$ queens on an $N \times N$ chessboard such that no two queens share the same row, column, or diagonal.2 A standard solution strategy is backtracking, which incrementally builds a partial arrangement, tests whether the latest placement is valid, and abandons any branch as soon as it violates the constraints.2

A compact way to represent a candidate solution is a one-dimensional array $Q$ where $Q[r] = c$ means “the queen in row $r$ is placed in column $c$.” This works because the algorithm places exactly one queen per row, so the remaining checks are only for column and diagonal conflicts.2

A square $(r,c)$ is unsafe if either:

• some earlier queen already uses column $c$, or
• some earlier queen lies on the same diagonal, which occurs when the row distance equals the column distance:

$$|Q[i] - c| = |i - r|$$

for some previously filled row $i$.2

The backtracking search is naturally a depth-first traversal of a recursion tree: each level corresponds to one row, each branch corresponds to a column choice, and dead ends are pruned immediately when no legal column exists.

Footnotes

1. Backtracking (University of Illinois CS473 notes) - Classical N-Queens backtracking pseudocode and recursion-tree interpretation. ↩ ↩² ↩³ ↩⁴ ↩⁵

2. N Queen Problem - GeeksforGeeks - Backtracking approaches, optimized hashing arrays, and stated complexity. ↩ ↩²

3. The N-queens Problem - Google OR-Tools - Constraint view of rows, columns, diagonals, and propagation/backtracking intuition. ↩

4. Algorithm of N queens - Stack Overflow - Clear explanation of recursive placement, backtracking behavior, and diagonal conflict logic. ↩

Problem structure and why backtracking fits

The problem has a strong constraint structure: each queen restricts future placements in its column and along two diagonals.2 Because a partial arrangement can already be known invalid before all rows are filled, backtracking is especially effective: it avoids exploring completions of impossible prefixes.2

There are two common pseudocode styles:

1. Naive safety check
   For each candidate $(r,c)$, scan all previously placed queens and test column and diagonal conflicts.

2. Optimized safety check with auxiliary arrays
   Maintain three Boolean structures:

   • cols[c] for used columns
   • diag1[r - c + n - 1] for one diagonal family
   • diag2[r + c] for the other diagonal family

The optimized form preserves the same backtracking logic but reduces each safety test to $O(1)$ time instead of scanning earlier rows.

A useful mathematical characterization is that queens share a diagonal exactly when either $r+c$ is equal or $r-c$ is equal. This is why diagonal occupancy can be stored with indexed arrays.2

Footnotes

1. N Queen Problem - GeeksforGeeks - Backtracking approaches, optimized hashing arrays, and stated complexity. ↩ ↩² ↩³ ↩⁴

2. Algorithm of N queens - Stack Overflow - Clear explanation of recursive placement, backtracking behavior, and diagonal conflict logic. ↩ ↩² ↩³

3. Backtracking (University of Illinois CS473 notes) - Classical N-Queens backtracking pseudocode and recursion-tree interpretation. ↩ ↩²

4. The N-queens Problem - Google OR-Tools - Constraint view of rows, columns, diagonals, and propagation/backtracking intuition. ↩

Canonical pseudocode

A classical row-wise version is shown below. It mirrors the recursive formulation used in algorithm texts.

1procedure PlaceQueens(Q, r, n):
2    if r = n + 1:
3        output Q
4        return
5
6    for c = 1 to n:
7        legal = true
8
9        for i = 1 to r - 1:
10            if Q[i] = c:
11                legal = false
12            else if abs(Q[i] - c) = abs(i - r):
13                legal = false
14
15        if legal:
16            Q[r] = c
17            PlaceQueens(Q, r + 1, n)

This pseudocode means:

• Q[r] = c stores the queen position for row r.
• The inner loop checks all previously placed queens only, because future rows are still empty.
• If no legal column exists for the current row, the function simply returns, and control goes back to the previous recursive call. That return is the “backtrack” step.2

An equivalent optimized pseudocode uses occupancy arrays:

1procedure Solve(row):
2    if row = n:
3        output current placement
4        return
5
6    for col = 0 to n - 1:
7        if cols[col] or diag1[row - col + n - 1] or diag2[row + col]:
8            continue
9
10        place queen at (row, col)
11        cols[col] = true
12        diag1[row - col + n - 1] = true
13        diag2[row + col] = true
14
15        Solve(row + 1)
16
17        remove queen at (row, col)
18        cols[col] = false
19        diag1[row - col + n - 1] = false
20        diag2[row + col] = false

This version is often preferred in implementations because the state needed for legality checks can be updated and reverted in constant time.

Footnotes

1. Backtracking (University of Illinois CS473 notes) - Classical N-Queens backtracking pseudocode and recursion-tree interpretation. ↩ ↩² ↩³ ↩⁴

2. The N-queens Problem - Google OR-Tools - Constraint view of rows, columns, diagonals, and propagation/backtracking intuition. ↩

3. N Queen Problem - GeeksforGeeks - Backtracking approaches, optimized hashing arrays, and stated complexity. ↩

How backtracking behaves on a 4-queens example

For $n=4$, one solution is $[2,4,1,3]$, meaning queens are placed at:

$$(1,2), (2,4), (3,1), (4,3)$$

This is a valid configuration because no two positions share a column, and for every pair of queens, the absolute row difference is not equal to the absolute column difference.2

A simplified execution sketch:

1. Try row 1, column 1.
2. Explore row 2 possibilities.
3. If row 3 cannot be filled legally, return to row 2 and try its next column.
4. If row 2 exhausts all columns, return to row 1 and try row 1, column 2.
5. Continue until a full arrangement is found.2

This illustrates the search principle: partial solutions are expanded only while they remain legal.

For $n=2$ and $n=3$, no solutions exist, so the backtracking tree is fully explored and every branch eventually fails. For $n=1$, a single queen is trivially a solution.

Footnotes

1. Backtracking (University of Illinois CS473 notes) - Classical N-Queens backtracking pseudocode and recursion-tree interpretation. ↩ ↩² ↩³

2. N Queen Problem - GeeksforGeeks - Backtracking approaches, optimized hashing arrays, and stated complexity. ↩ ↩² ↩³

3. The N-queens Problem - Google OR-Tools - Constraint view of rows, columns, diagonals, and propagation/backtracking intuition. ↩

Time and space complexity

The worst-case time complexity is commonly described as $O(n!)$ for the backtracking formulation, because the algorithm places one queen per row and the number of feasible column choices shrinks as rows are filled; pruning prevents unrestricted $n^n$ growth in the usual row-wise formulation.2 However, the exact number of explored nodes depends heavily on how early conflicts are detected and on the value of $n$.2

There is also an important implementation distinction:

• Naive safety scan
  Each candidate may require checking up to $r-1$ earlier queens, so the constant factors are larger.

• Hashed/array-based safety check
  Column and diagonal occupancy tests become $O(1)$ per candidate, improving practical speed while keeping the same exponential search structure.

Typical auxiliary space is:

• $O(n)$ for the recursion stack and the placement/occupancy arrays in the optimized variant,
• or $O(n^2)$ if an explicit board matrix is stored in a simple implementation.

Footnotes

1. N Queen Problem - GeeksforGeeks - Backtracking approaches, optimized hashing arrays, and stated complexity. ↩ ↩² ↩³ ↩⁴ ↩⁵

2. Time complexity of N Queen using backtracking? - Stack Overflow - Discussion supporting the common $O(n!)$ worst-case characterization. ↩ ↩²

3. Backtracking (University of Illinois CS473 notes) - Classical N-Queens backtracking pseudocode and recursion-tree interpretation. ↩

Final interpretation of the pseudocode

The N-Queens backtracking pseudocode is best understood as a recursive search over partial solutions.2 At row $r$, the algorithm tries every column, keeps only placements consistent with rows $1$ through $r-1$, and recursively solves the smaller subproblem for row $r+1$. If no candidate works, the function returns to its caller, effectively undoing the previous decision and exploring a different branch.2

In conceptual terms, the pseudocode embodies three ideas:

1. Constructive search: build a solution one row at a time.
2. Constraint checking: reject illegal partial states immediately.2
3. Systematic reversal: undo choices and continue until all possibilities are exhausted or a desired solution is found.2

That is exactly why N-Queens is considered a canonical example of backtracking in algorithm design.2

Footnotes

1. Backtracking (University of Illinois CS473 notes) - Classical N-Queens backtracking pseudocode and recursion-tree interpretation. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶

2. The N-queens Problem - Google OR-Tools - Constraint view of rows, columns, diagonals, and propagation/backtracking intuition. ↩ ↩² ↩³

3. N Queen Problem - GeeksforGeeks - Backtracking approaches, optimized hashing arrays, and stated complexity. ↩ ↩²

4. Algorithm of N queens - Stack Overflow - Clear explanation of recursive placement, backtracking behavior, and diagonal conflict logic. ↩