The N-Queens Problem in Python: Backtracking at Its Clearest

Put eight queens on a chessboard so that none of them can capture another. That is the entire problem, posed by the chess composer Max Bezzel in 1848, and it has outlived almost every other puzzle of its era for one reason: it is the cleanest demonstration of backtracking anyone has found. The general version swaps eight for n — place n queens on an n by n board with no two sharing a row, a column or a diagonal.

The reason it is worth your time is the gap between the obvious approach and the good one. Choosing 8 squares out of 64 gives 4,426,165,368 boards to test. The good version examines 2,057 partial boards and finds all 92 solutions. Nothing clever was added to get there — the entire improvement comes from two things: describing the board in a way that makes illegal positions unrepresentable, and abandoning a branch the instant it becomes hopeless.

Be clear about what this is, though. N-queens is a benchmark and a teaching problem, not a production algorithm. If you only need one solution for large n there are closed-form constructions that place the queens directly in O(n) time with no search at all. Backtracking earns its place when you need every solution, an exact count, or the freedom to bolt extra constraints onto the search.

The idea

A queen attacks along four lines at once: her whole row, her whole column, and both diagonals running through her square. Every square on any of those lines is off limits to every other queen.

Look at how much one queen destroys. On a 4 by 4 board a queen placed near the middle attacks 11 of the other 15 squares, leaving 4. That destructiveness is why the naive search space is such a lie: almost none of it is reachable.

Start counting anyway, because the numbers are what justify everything that follows.

from math import comb, factorial

for n in (4, 6, 8):
    squares = n * n
    print(f"n = {n}:  {comb(squares, n):>13,}  boards with n queens dropped anywhere")
    print(f"        {n ** n:>13,}  boards with exactly one queen per row")
    print(f"        {factorial(n):>13,}  boards with one per row and one per column")

n = 4:          1,820  boards with n queens dropped anywhere
                  256  boards with exactly one queen per row
                   24  boards with one per row and one per column
n = 6:      1,947,792  boards with n queens dropped anywhere
               46,656  boards with exactly one queen per row
                  720  boards with one per row and one per column
n = 8:  4,426,165,368  boards with n queens dropped anywhere
           16,777,216  boards with exactly one queen per row
               40,320  boards with one per row and one per column

Two observations collapse that first column into the third, and both are worth stating precisely because they do all the work.

Exactly one queen goes in every row. There are n queens and n rows, and two queens in the same row would attack each other, so no row can hold two. n queens spread over n rows with at most one each means every row holds exactly one. So a candidate board is fully described by n numbers: for each row, which column its queen sits in. That single change takes 4.4 billion boards down to 16.7 million for n = 8.

No column is used twice either, by exactly the same argument. So those n numbers are a permutation of 0 through n − 1. That takes 16.7 million down to 40,320.

Everything left is diagonals. And rather than generate all 40,320 permutations and filter them, build the permutation one row at a time and reject as early as possible: place a queen in row 0, then row 1, then row 2, and the moment a row has no legal square, throw away the last queen and try the next column for it instead.

That removal step is what makes it backtracking rather than plain recursion. The board must be restored to exactly its previous state before the next column is tried, or later branches inherit queens that are no longer there.

Naming the diagonals

The whole algorithm now rests on one question, asked once per candidate square: is this square attacked by any queen already placed? If answering it costs a scan over the placed queens, that is O(n) per square and O(n²) per row. There is a much better way.

Give every diagonal a name. Walk one step down and to the right, and both the row and the column go up by one, so row - col does not change. That means every square on a \ diagonal shares one value of row - col, and squares on different \ diagonals never do.

The other direction works the same way with the other sign. Walk one step down and to the left and the row goes up by one while the column goes down by one, so row + col does not change. Every / diagonal has its own constant value of row + col.

On an n by n board row - col ranges from −(n − 1) to n − 1 and row + col ranges from 0 to 2n − 2 — 2n − 1 diagonals in each direction, 30 in total for a chessboard. So keep three sets:

• used_columns — the columns already holding a queen.
• used_down_diagonals — the row - col values already taken.
• used_up_diagonals — the row + col values already taken.

A square at (row, col) is safe exactly when col, row - col and row + col are all absent from their respective sets. Three set lookups, each O(1) on average because Python hashes small integers to themselves. No scan, no matter how many queens are already down. That is the trick the whole implementation is built on.

Watching it work

Take n = 4 and follow the search exactly as the code will run it, always trying columns left to right.

Row 0, column 0. The sets become columns {0}, down {0}, up {0}.

Row 1. Column 0 is a used column. Column 1 has row - col = 0, already taken by the queen at (0, 0) — they are on the same \ diagonal. Column 2 is clear on all three counts, so the queen goes there. The sets are now columns {0, 2}, down {0, -1}, up {0, 3}.

Row 2. Every square fails:

• Column 0 — the column is used.
• Column 1 — row + col = 3, which the queen at (1, 2) already owns.
• Column 2 — the column is used.
• Column 3 — row - col = -1, which the queen at (1, 2) already owns.

That is the first backtrack. The search returns to row 1, removes the queen from column 2 — restoring the sets to columns {0}, down {0}, up {0} — and tries column 3 instead.

From there it gets one row further. Row 2 accepts column 1, then row 3 has nothing left: columns 0, 3 and 1 are used, and column 2 sits on row - col = 1, which the queen at (2, 1) owns. Back up to row 2 — column 2 lies on the same \ diagonal as the queen at (0, 0) and column 3 is taken, so row 2 is finished too. Row 1 then runs out of columns. The entire subtree under "row 0, column 0" contains no solution, and the search finally moves the first queen to column 1.

That branch works out immediately: row 1 takes column 3, row 2 takes column 0, row 3 takes column 2. Four queens, no conflicts, first solution found.

The remaining two branches are mirror images of the first two: column 2 mirrors column 1 and yields the second solution, column 3 mirrors column 0 and yields nothing. Seventeen partial boards examined in total, against 24 permutations and 1,820 raw placements.

The code

Start with the version that follows straight from the counting above: generate every permutation of the columns, then check the diagonals. It is short, obviously correct, and a useful reference to test the fast version against.

from itertools import permutations


def is_safe_arrangement(columns: tuple[int, ...]) -> bool:
    """True when no two queens in a one-per-row, one-per-column board share a diagonal."""
    for upper in range(len(columns)):
        for lower in range(upper + 1, len(columns)):
            # Two queens share a diagonal when the row gap equals the column gap.
            if lower - upper == abs(columns[lower] - columns[upper]):
                return False
    return True


def count_by_permutation(n: int) -> int:
    """Count solutions by testing every column permutation. Correct, and wasteful."""
    return sum(1 for columns in permutations(range(n)) if is_safe_arrangement(columns))


for n in range(4, 9):
    print(f"n = {n}: {count_by_permutation(n):>3} solutions from {factorial(n):>6,} permutations")

n = 4:   2 solutions from     24 permutations
n = 5:  10 solutions from    120 permutations
n = 6:   4 solutions from    720 permutations
n = 7:  40 solutions from  5,040 permutations
n = 8:  92 solutions from 40,320 permutations

Those are the right answers — 92 for the classic eight-queens board — and note that the counts are not monotonic: six queens have only 4 solutions where five queens have 10. The problem is spikier than it looks.

This version dies quickly, though. permutations is a generator, so it hands the boards over one at a time rather than materialising all of them — but it still hands over every one of the n!, and nothing is judged until all n queens are already placed. n = 12 means 479 million full boards, and n = 15 means over a trillion. Worse, it learns nothing from failure: for n = 8 a permutation starting 0, 1 already has two queens on the same diagonal, but the loop still produces all 720 completions of that prefix and tests every one of them from scratch.

Backtracking fixes precisely that. Build the permutation left to right and check each queen against the ones already placed, so a doomed prefix is abandoned once instead of re-derived thousands of times.

def solve_n_queens(n: int) -> list[list[int]]:
    """Every placement of n queens on an n by n board with no two attacking.

    A solution is a list of n column indices: entry r holds the column of the
    queen in row r. One queen per row is baked into the shape of the answer,
    so the search never considers anything else.
    """
    solutions: list[list[int]] = []
    used_columns: set[int] = set()
    used_down_diagonals: set[int] = set()   # row - col is constant along a "\" line
    used_up_diagonals: set[int] = set()     # row + col is constant along a "/" line
    placement: list[int] = []

    def place_queen_in(row: int) -> None:
        if row == n:
            # Every row is filled, so this partial board is a complete solution.
            solutions.append(placement.copy())
            return

        for col in range(n):
            if (col in used_columns
                    or row - col in used_down_diagonals
                    or row + col in used_up_diagonals):
                continue

            used_columns.add(col)
            used_down_diagonals.add(row - col)
            used_up_diagonals.add(row + col)
            placement.append(col)

            place_queen_in(row + 1)

            # Undo before trying the next column, so the three sets always
            # describe exactly the queens still standing on the board.
            placement.pop()
            used_up_diagonals.remove(row + col)
            used_down_diagonals.remove(row - col)
            used_columns.remove(col)

    place_queen_in(0)
    return solutions


print(solve_n_queens(4))
print(f"n = 1: {solve_n_queens(1)}   n = 2: {solve_n_queens(2)}   n = 3: {solve_n_queens(3)}")

[[1, 3, 0, 2], [2, 0, 3, 1]]
n = 1: [[0]]   n = 2: []   n = 3: []

The two solutions for n = 4 are the ones traced by hand above, in the order the search finds them. The small boards behave correctly with no special cases: one queen on a 1 by 1 board is trivially fine, and 2 and 3 genuinely have no solutions, which the code discovers by exhausting the search rather than by being told.

A list of column indices is a compact answer but a poor picture, so draw it.

def render(solution: list[int]) -> str:
    """Draw one solution: Q for a queen, . for an empty square."""
    return "\n".join(
        " ".join("Q" if col == queen_col else "." for col in range(len(solution)))
        for queen_col in solution
    )


for number, solution in enumerate(solve_n_queens(4), start=1):
    print(f"n = 4, solution {number}: columns {solution}")
    print(render(solution))

first_eight = solve_n_queens(8)[0]
print(f"n = 8, first solution: columns {first_eight}")
print(render(first_eight))

n = 4, solution 1: columns [1, 3, 0, 2]
. Q . .
. . . Q
Q . . .
. . Q .
n = 4, solution 2: columns [2, 0, 3, 1]
. . Q .
Q . . .
. . . Q
. Q . .
n = 8, first solution: columns [0, 4, 7, 5, 2, 6, 1, 3]
Q . . . . . . .
. . . . Q . . .
. . . . . . . Q
. . . . . Q . .
. . Q . . . . .
. . . . . . Q .
. Q . . . . . .
. . . Q . . . .

How the code maps to the idea

The row parameter is the recursion depth. There is no loop over rows anywhere, because "one queen per row" is expressed by the structure of the recursion: each call handles exactly one row, and place_queen_in(row + 1) moves to the next. Nothing in the code can produce a board with two queens in a row, so no check for it exists.

The base case is row == n. Reaching it means all n rows were filled without a conflict, so the current placement is a solution. There is no validity test at the bottom — every queen was checked before it was placed, so a complete board is correct by construction.

placement.copy() is load-bearing. placement is one list that the search mutates for the whole run. Appending it directly would store one more reference to that same list every time a solution is found — 92 of them for n = 8 — and the list is emptied again on the way out, so every one of those references ends up pointing at []. Copy it, or the function returns a pile of aliases to nothing.

The continue is the pruning. When a square fails the three-set test, no queen is placed and no recursion happens, so every board that would have grown out of that square is skipped. That is the entire performance story — the whole subtree disappears from one if.

The three remove calls are the backtrack. They mirror the three add calls, undoing them in reverse order. The order does not matter functionally — the three sets are independent — but mirroring makes it obvious that nothing was missed. Forget one and the sets slowly fill with ghosts, and the search silently reports too few solutions.

The nested function closes over the sets, so every recursive call shares one copy of each. Passing copies down would also be correct, and would cost O(n) per call for nothing. Depth is only n + 1 frames, so Python's 1,000-frame recursion limit never binds.

Complexity

The honest headline: the upper bound is loose, the real cost is much smaller, and nobody can state the real cost exactly.

The upper bound. Because the search fixes one queen per row and never repeats a column, the nodes at depth k are at most n × (n − 1) × … × (n − k + 1), which is n! / (n − k)!. Summing over all depths gives a total node count of at most

n! × (1/0! + 1/1! + … + 1/n!), which is less than e × n! ≈ 2.72 n!.

Each node loops over n columns and does three O(1) set lookups per column, so the work per node is O(n). Multiply: O(n × n!) in the worst case, and that is genuinely an upper bound rather than a description of what happens.

What actually happens. The pruning removes most of that tree, and there is no known closed form for how much. So measure it.

def count_n_queens(n: int) -> tuple[int, int]:
    """Return (number of solutions, number of partial boards the search examined)."""
    used_columns: set[int] = set()
    used_down_diagonals: set[int] = set()
    used_up_diagonals: set[int] = set()
    boards_examined = 0

    def place_queen_in(row: int) -> int:
        nonlocal boards_examined
        boards_examined += 1
        if row == n:
            return 1

        found = 0
        for col in range(n):
            if (col in used_columns
                    or row - col in used_down_diagonals
                    or row + col in used_up_diagonals):
                continue

            used_columns.add(col)
            used_down_diagonals.add(row - col)
            used_up_diagonals.add(row + col)
            found += place_queen_in(row + 1)
            used_up_diagonals.remove(row + col)
            used_down_diagonals.remove(row - col)
            used_columns.remove(col)

        return found

    return place_queen_in(0), boards_examined


print(f"{'n':>3} {'solutions':>10} {'boards examined':>16} {'n!':>14}")
for n in range(4, 13):
    solutions, boards = count_n_queens(n)
    print(f"{n:>3} {solutions:>10,} {boards:>16,} {factorial(n):>14,}")

  n  solutions  boards examined             n!
  4          2               17             24
  5         10               54            120
  6          4              153            720
  7         40              552          5,040
  8         92            2,057         40,320
  9        352            8,394        362,880
 10        724           35,539      3,628,800
 11      2,680          166,926     39,916,800
 12     14,200          856,189    479,001,600

At n = 12 the bound allows about 1.3 billion nodes and the search examines 856,189 — roughly 1,500 times fewer. But watch the ratios down that middle column: 2,057, then 8,394, then 35,539, then 166,926, then 856,189. Each step multiplies the work by more than the step before it: 4.1×, then 4.2×, then 4.7×, then 5.1×. Pruning changed the constant and the base, not the shape: the growth is still worse than exponential. On this code n = 14 already takes minutes and n = 15 tens of minutes, and n = 20 is out of reach no matter how long you wait.

Space: O(n). The recursion is n + 1 frames deep and the three sets hold at most n entries each. count_n_queens therefore runs in linear space no matter how astronomically many solutions it counts. solve_n_queens is different — it stores every solution, so its memory is O(n × number of solutions), which for n = 12 is 14,200 lists of 12 integers. If you only want the count, count.

One more honest note: counting solutions is far harder than finding one. The exact totals are known only up to n = 27, and that value was produced in 2016 by a distributed FPGA project that ran for about a year. No formula for the sequence is known.

When to use it, and when not to

Use backtracking for n-queens when you want all solutions, an exact count, or a solution satisfying extra constraints you invented ("no queen on the main diagonal", "these three squares must be occupied"). It is also the right shape for the whole family of constraint puzzles — Sudoku, graph colouring, crosswords, the knight's tour — where the three-set pattern generalises directly.

Do not use it to find a single solution for large n. Explicit constructions exist that place n non-attacking queens for every n ≥ 4 in O(n) time by writing the column indices from a formula, with no search whatsoever. If all you need is one valid board, searching for it is the wrong tool by an enormous margin.

Do not use it for very large n even with the constraints relaxed. Local search beats it badly here: the min-conflicts heuristic starts from a random full board, picks a queen that is currently under attack, and moves it within its own column to the square that conflicts with the fewest others. It solves the million-queens problem in around fifty moves on average. Backtracking cannot get past a few dozen.

Do not hand-roll it when the constraints get complicated. Once the rules stop being three simple sets, a real constraint solver — Google's OR-Tools CP-SAT, or a SAT solver — will out-prune anything you write by hand, because it learns from conflicts instead of just backing up one level.

And if the search tree has overlapping subproblems rather than merely infeasible ones, backtracking is the wrong family entirely; that is what dynamic programming is for. N-queens has a trace of overlap: on an 8 by 8 board the prefixes 1, 3, 0, 2 and 2, 0, 3, 1 block exactly the same columns and the same diagonals, so rows 4 through 7 face an identical subproblem. There is far too little of it to pay for a memo table, though. The key would have to be a set of columns plus two sets of diagonals, and that key repeats so rarely that the cache needs an entry for very nearly every node — for which it cuts n = 8 from 2,057 nodes to 1,999, and n = 12 from 856,189 to 821,299. Under five per cent of the work saved, for a table almost as large as the search itself. Plain backtracking stays the right family here.

Where it shows up in the real world

Not as itself. Nobody ships software that places queens on chessboards.

What it has instead is a real career as a proving ground. Niklaus Wirth built his 1971 paper Program Development by Stepwise Refinement — one of the founding documents of structured programming — around the eight queens problem, and the modern shape of this algorithm is essentially his. Constraint toolkits including Google's OR-Tools and MiniZinc ship it as a standard example, because everyone already knows the answers, so a new solver can be checked against them. Russell and Norvig's Artificial Intelligence: A Modern Approach uses it as the running example for local search, which is where the million-queens figure comes from.

The transferable part is the pattern, and that does ship. A Sudoku solver is this algorithm with different bookkeeping: three collections of used digits, one per row, one per column and one per 3 by 3 box, with the same place-recurse-undo cycle around them. Once you can write n-queens without thinking, you can write that in twenty minutes.

Common mistakes

Forgetting to undo. Leave out one of the three remove calls and the sets fill with queens that are no longer on the board. Nothing crashes; the search just reports too few solutions. Drop the down-diagonal remove and n = 8 comes back as 0 rather than 92, because the ghosts block every branch the search tries after its first retreat.

Storing the live list. solutions.append(placement) instead of solutions.append(placement.copy()) stores the same object every time. You get one reference per solution — 92 of them at n = 8 — all pointing at the same list, and that list is empty by the time the search returns, so the answer prints as ninety-two copies of [].

Using the same expression for both diagonals. If used_down is also fed row + col, the code compiles, runs, and reports 2,113 solutions for n = 8 — it is now only checking columns and one diagonal direction. Always check n = 8 against 92; it is the cheapest regression test in the world.

Sizing the diagonal arrays by n. Swapping the sets for boolean lists is a reasonable optimisation, but there are 2n − 1 diagonals in each direction, not n. Allocating [False] * n and indexing it by row - col raises nothing, because Python reads negative indices from the end — diagonal v and diagonal v − n end up sharing a slot, so the search blocks squares it should not and under-counts. That does not fail loudly and it does not fail uniformly: n = 8 comes back as 0 instead of 92 and n = 9 as 116 instead of 352, but n = 5 comes back as 10, which is the correct answer. Test the bug on a small odd board and it passes. A list of length exactly 2 * n - 1 does work, since the negative wrap covers exactly one period, but used_down[row - col + n - 1] on the same list is the version you can reread in six months.

Scanning the placed queens for every candidate square. Looping over placement and testing abs(row - other_row) == abs(col - other_col) is correct and is what the permutation version does. It also turns an O(1) check into an O(n) one, which multiplies the whole runtime by n for no benefit.

Checking rows. Some implementations carry a used_rows set. It can never fire — the recursion visits each row exactly once — so it is pure overhead, and its presence usually signals a misunderstanding of why the one-queen-per-row rule was free.

Practice

1. Add an early return so the search stops at the first solution instead of enumerating all of them, and confirm it returns [1, 3, 0, 2] for n = 4.
2. Replace the three sets with three boolean lists, remembering the + n - 1 shift for the down diagonals, and check that every count from n = 4 to n = 10 is unchanged.
3. Print how many of the 92 eight-queens solutions have a queen in the corner square, using the rendering function to spot-check a few by eye.
4. For even n, restrict the queen in row 0 to the left half of the board and double the resulting count; verify it matches the full search for n = 8, 10 and 12, and work out why the trick needs care for odd n.
5. Reuse the place-recurse-undo skeleton to solve a 9 by 9 Sudoku, tracking used digits per row, per column and per 3 by 3 box.

Summary

N-queens is the problem to reach for when you want to understand backtracking, because every part of it is visible. The search space shrinks from 4.4 billion to 40,320 through two sentences of reasoning, the conflict test collapses to three O(1) lookups because row - col and row + col name the diagonals, and the pruning turns an intractable bound into 2,057 examined boards. Learn the three-set trick properly; you will use it again the next time a puzzle has "no two of these may share a line" in its rules.

Keep reading

• Recursion and Backtracking in Python — the mental model this post applies, built from scratch.
• Depth-First Search — the same traversal, run over an explicit graph instead of an implicit search tree.
• Hash Tables in Python — why those three set lookups really are O(1), and when they are not.
• Dynamic Programming Explained — what to do instead when the branches of the search overlap.
• Big O Notation — the counting argument behind the n! bound above.