Introduction

The backtracking solution to the N-Queens problem is exponential, and the standard worst-case description is O(N!). That bound is not a claim that the algorithm literally explores every permutation in every run, but it is the right high-level way to express how the search space grows when you place queens row by row while forbidding reused columns.

Why the Search Space Looks Factorial

A typical backtracking solver places one queen per row. For each row, it tries columns that are not already occupied and also checks diagonals.

If you ignore diagonal pruning for a moment, the branching pattern looks like this:

• first row: up to N choices
• second row: up to N - 1 remaining columns
• third row: up to N - 2
• and so on

Multiplying those choices gives N!.

Diagonal constraints prune many branches earlier, which is why the solver is usually faster than a naive permutation scan in practice, but the algorithm is still exponential in growth and the common worst-case description remains factorial.

A Standard Backtracking Implementation

A compact Python implementation makes the structure clear.

1
2def solve_n_queens(n):
3    cols = set()
4    diag1 = set()  # row - col
5    diag2 = set()  # row + col
6    solutions = []
7    board = [-1] * n
8
9    def backtrack(row):
10        if row == n:
11            solutions.append(board.copy())
12            return
13
14        for col in range(n):
15            if col in cols or (row - col) in diag1 or (row + col) in diag2:
16                continue
17
18            cols.add(col)
19            diag1.add(row - col)
20            diag2.add(row + col)
21            board[row] = col
22
23            backtrack(row + 1)
24
25            cols.remove(col)
26            diag1.remove(row - col)
27            diag2.remove(row + col)
28            board[row] = -1
29
30    backtrack(0)
31    return solutions
32
33
34print(len(solve_n_queens(8)))

The recursive structure is what drives the complexity: each valid partial placement spawns more candidate placements until the branch dies or becomes a full solution.

Why It Is Not N^N

You will sometimes see people say the complexity is O(N^N) because each row could try N columns. That is too loose for the standard row-by-row formulation because once a column is occupied, it is not tried again in deeper rows.

So O(N!) is the tighter common bound for the classic backtracking approach with one queen per row and one queen per column.

The diagonal checks do not change the factorial nature of the upper bound. They only reduce the practical search space.

Space Complexity

The auxiliary space cost is much smaller than the time cost.

A standard recursive solver stores:

• recursion depth up to N
• occupied columns
• occupied diagonals
• the current partial board

That leads to O(N) additional space, excluding the space used to store all solutions if you keep them.

If you store every valid solution, total output space can become much larger, but that is output cost rather than working memory for the search itself.

Practical Performance

Although the asymptotic bound is harsh, good constant-factor implementation choices matter.

Common speedups include:

• using boolean arrays or bitmasks instead of Python sets
• exploiting symmetry for the first row
• stopping after the first solution instead of enumerating all solutions

These improvements help real runtime significantly, but they do not change the underlying exponential character of the problem.

Common Pitfalls

Calling the algorithm polynomial because each step checks only a few constraints is a conceptual mistake. The recursion tree is the real cost driver.

Saying the complexity is exactly N! is also too strong. O(N!) is an upper-bound style summary, not an exact runtime formula for every implementation and input size.

Ignoring the difference between finding one solution and enumerating all solutions can also confuse the discussion. Enumerating all solutions is naturally more expensive.

Finally, do not mix output size with working memory. Time is exponential, while the typical backtracking working space is only linear in N.

Summary

• the classic row-by-row backtracking solver for N-Queens is commonly described as O(N!) in worst-case time
• that bound comes from choosing distinct columns across rows, with diagonal pruning reducing many branches in practice
• the algorithm is exponential even though individual safety checks are cheap
• working memory is usually O(N) excluding stored solutions
• optimizations improve practical speed, but they do not change the fundamental exponential search behavior