Introduction

The right answer depends on which version of the N-Queens problem you mean. The decision problem, the constructive problem, and the counting problem look similar on the surface, but their complexity is very different.

The First Important Distinction

People often ask for the complexity of "the N-Queens puzzle" as if there were only one task. In practice there are at least three common tasks:

• decide whether a solution exists for size N
• construct one valid arrangement
• count all valid arrangements

Those are not the same problem.

Decision Complexity Is Trivial

If the question is only "does an N x N board have a solution," there is a simple theorem:

• 'N = 1 has a solution'
• 'N = 2 and N = 3 do not'
• every N >= 4 has at least one solution

So the decision problem can be answered in constant time once you know this result.

1def has_n_queens_solution(n: int) -> bool:
2    return n == 1 or n >= 4
3
4
5for n in range(1, 9):
6    print(n, has_n_queens_solution(n))

From a strict complexity point of view, that is O(1) decision time.

Constructing One Solution Can Be Done Efficiently

If the task is to produce one valid board, you do not need an exhaustive search for every N. There are constructive patterns that build a valid arrangement for all solvable sizes.

That means the "find one solution" version is much better than the usual backtracking presentation suggests. In principle, you can construct a solution in linear or near-linear time depending on the exact method and representation.

A simple educational approach is still backtracking because it is easy to understand:

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

This works well for moderate N, but its worst-case search behavior is still exponential.

Why Backtracking Is Usually Quoted As O(N!)

The classic search places one queen per row and tries unused columns. In the worst case, that resembles exploring permutations of columns, giving an upper bound around O(N!).

That is not a tight mathematical statement for every optimized implementation, but it is the standard practical description: exhaustive search grows exponentially and becomes expensive quickly.

Optimizations such as:

• diagonal conflict sets
• bit masks
• symmetry pruning

make the solver much faster in practice, but they do not turn exhaustive enumeration into a polynomial-time algorithm.

Counting All Solutions Is The Expensive Version

If the goal is to count every valid arrangement, the problem is fundamentally harder than just finding one.

A backtracking counter looks like this:

1def count_n_queens(n: int) -> int:
2    cols = set()
3    diag1 = set()
4    diag2 = set()
5    total = 0
6
7    def backtrack(row: int):
8        nonlocal total
9        if row == n:
10            total += 1
11            return
12
13        for col in range(n):
14            if col in cols or (row - col) in diag1 or (row + col) in diag2:
15                continue
16
17            cols.add(col)
18            diag1.add(row - col)
19            diag2.add(row + col)
20            backtrack(row + 1)
21            cols.remove(col)
22            diag1.remove(row - col)
23            diag2.remove(row + col)
24
25    backtrack(0)
26    return total
27
28
29print(count_n_queens(8))

This is the version where exponential growth is unavoidable in any straightforward exact solver, because you must explore a huge search space to enumerate or count all valid boards.

So What Is The "Best Complexity"?

The best answer is:

• decision: O(1) once the existence result is known
• construct one solution: efficient constructive methods exist, much better than brute-force search
• count or enumerate all solutions: exponential-time search in practice

That is why a single number like O(N!) is incomplete. It describes the common backtracking solver, not every formulation of the problem.

Common Pitfalls

The most common mistake is quoting O(N!) without saying which problem is being solved. That is fine for naïve exhaustive search, but wrong for the decision version.

Another mistake is assuming "find one solution" and "count all solutions" have roughly the same complexity. They do not.

People also confuse asymptotic complexity with practical runtime. Bit-mask solvers can be dramatically faster than textbook backtracking even though the problem still has exponential search structure in the exhaustive case.

Finally, do not use small examples such as N = 8 to make claims about asymptotic behavior. The interesting difficulty appears as N grows.

Summary

• N-Queens has multiple problem formulations, and their complexities differ.
• Deciding existence is O(1) because solutions exist for N = 1 and all N >= 4.
• Constructing one solution can be done efficiently with constructive methods.
• Exhaustively counting or enumerating solutions is exponential in practice.
• 'O(N!) is a useful description for classic backtracking, not a universal answer for every version of N-Queens.'