N-Queens Explained: Backtracking With Pruning

Place n queens on an n × n chessboard so that no two attack each other. N-Queens is the classic backtracking problem because it shows the whole technique in one place: a decision tree far too large to enumerate, a cheap test that kills most of it early, and an undo step that makes the search possible on a single shared board.

The problem it solves

Two queens attack if they share a row, a column or a diagonal. The task is usually one of two versions: return every valid board, or just count them. For n = 8 there are 92 solutions.

The naive approach — try every way to put n queens on n² squares and check each board — is hopeless. For n = 8 that is more than four billion placements. The whole point of the problem is to not look at most of them.

The intuition

Two observations shrink the search.

One queen per row. Two queens in the same row always attack, and there are exactly n rows for n queens, so every solution has one queen in each row. The problem becomes a sequence of n decisions: which column for row 0, which for row 1, and so on. That is at most nⁿ paths instead of billions of boards.

Stop as soon as a row is hopeless. Place queens row by row. Before placing one, check whether the square is attacked by any queen above it. If every square in the current row is attacked, the partial board above cannot be completed — so return, and let the previous row try its next column. That early return is the pruning, and it is where almost all the savings come from.

The attack check has to be fast. Columns are easy: keep a set of claimed columns. Diagonals have a neat property: along a down-right diagonal, row - col is constant; along an up-right one, row + col is constant. So two more sets, keyed by those numbers, answer "is this diagonal taken?" in O(1).

Watch it run

The animation runs the real 4-queens search. Row 0 takes column 0 and crosses out everything it attacks. Row 1 lands on column 2, and row 2 is then attacked on every square — a dead end. Row 1 slides to column 3, row 3 dies instead, and the search unwinds to move the row-0 queen. From column 1 the rows fall into place and the board is solved.

The code

A solver that returns every board as a list of column positions, one per row, and counts how many squares it tested:

def solve_n_queens(n):
    cols, down, up = set(), set(), set()     # claimed column, r - c, r + c
    queens, solutions = [], []
    tried = 0

    def place(row):
        nonlocal tried
        if row == n:                           # every row has a queen
            solutions.append(queens[:])
            return
        for c in range(n):
            tried += 1
            if c in cols or row - c in down or row + c in up:
                continue                       # attacked: prune this square
            cols.add(c); down.add(row - c); up.add(row + c); queens.append(c)
            place(row + 1)
            cols.discard(c); down.discard(row - c); up.discard(row + c); queens.pop()

    place(0)
    return solutions, tried

sols, tried = solve_n_queens(4)
print(sols, tried)                             # [[1, 3, 0, 2], [2, 0, 3, 1]] 60
for c in sols[0]:
    print("".join("Q" if i == c else "." for i in range(4)))
# .Q..
# ...Q
# Q...
# ..Q.

Sixty squares were tested to find both solutions to the 4 × 4 board. The animation stops at the first solution, which takes fewer.

Here is the same solver for n from 1 to 10, printing n, the number of solutions, the squares tested and nⁿ, the number of one-queen-per-row boards:

for n in range(1, 11):
    sols, tried = solve_n_queens(n)
    print(n, len(sols), tried, n ** n)
# 1 1 1 1
# 2 0 6 4
# 3 0 18 27
# 4 2 60 256
# 5 10 220 3125
# 6 4 894 46656
# 7 40 3584 823543
# 8 92 15720 16777216
# 9 352 72378 387420489
# 10 724 348150 10000000000

For n = 8, pruning tests 15,720 squares, while the one-per-row space holds almost 17 million boards. The gap widens with every n. Notice also that 2 and 3 have no solution at all, and that the count is not monotonic: six queens have fewer solutions than five.

To check the solver, a slower reference tries every column order — every permutation, which already guarantees distinct rows and columns — and keeps those where all row - col and all row + col values are distinct:

import itertools

def brute(n):                                  # every column order, then check diagonals
    count = 0
    for perm in itertools.permutations(range(n)):
        if len({r - c for r, c in enumerate(perm)}) == n and \
           len({r + c for r, c in enumerate(perm)}) == n:
            count += 1
    return count

print(all(len(solve_n_queens(n)[0]) == brute(n) for n in range(1, 10)))   # True

The reference examines all n! orders — 362,880 of them for n = 9 — and agrees with the backtracking solver for every n up to 9.

The complexity

No simple closed-form bound is tight. A common upper bound is O(n!): row 0 has n choices, row 1 at most n - 1 free columns, and so on, and each step does O(1) set work plus O(n) to copy a solution. In practice the diagonal checks prune far more than the column check alone: for n = 10 the solver tests about 350,000 squares, under a tenth of 10!, which is 3,628,800. Extra space is O(n): three sets, the queen list and the recursion depth.

Where it goes wrong

• Scanning the board to test a square. Walking up the column and both diagonals costs O(n) per test. The three sets make it O(1).
• Mixing up the diagonal keys. One set is row - col, the other row + col. Using the same key for both lets queens sit on a shared diagonal.
• Forgetting to release a square. The three discard calls must mirror the three add calls, or later branches see phantom queens and miss solutions.
• Building strings too early. Store column indices during the search and draw the board only for the final answers.

How to say it in an interview

"Every row holds exactly one queen, so I place queens row by row and only choose a column. A square is attacked if its column, its row - col diagonal or its row + col diagonal is already claimed, and I keep three sets for those. If a row has no safe column, I backtrack to the previous row. Space is O(n); time is exponential, bounded by roughly O(n!), but pruning keeps the real search tiny compared with the full board space."

This is the same choose, explore, un-choose loop as in generating subsets, with a test that cuts branches before they grow.