Complexity

Our first solution generated every possible board with one queen per row:

n**n

Then, for each board, we ran a full validation that compares pairs of queens, which is O(n^2).

Multiply those together and the brute-force approach lands at roughly:

O(n^n * n^2)

It also needs tons of memory because it builds the full list of candidate boards before filtering them.

Backtracking never builds all those boards. It grows one partial board and abandons bad paths the moment they go wrong. And because we never allow two queens in the same column, the search is closer to trying permutations of columns:

n!

That's a dramatically smaller space than n^n.

In our first backtracking version, each safety check scanned the partial board (up to O(n)), and we looped over columns at each row. A loose upper bound is:

O(n! * n^2)

Still exponential, but a massive improvement over brute force.

The final version swaps that board scan for sets that track used columns and diagonals, making each safety check O(1) on average:

col in used_cols
row + col in used_up_diagonals
row - col in used_down_diagonals

The search is still exponential because N Queens is still a combinatorial problem, but the upper bound tightens to:

O(n! * n)

The key improvement is that each safety check is much cheaper, which makes a big difference in practice.

If we ignore the space used to store the solutions themselves, both backtracking versions need only O(n) working space:

• The current board holds at most n columns.
• The recursive call stack is at most n calls deep.
• The used sets in the pruned version each hold at most n values.

That said, solve_n_queens returns every solution. If there are s valid boards, the returned list takes:

O(s * n)

That's not a flaw in the algorithm; it's just the cost of returning all the answers.