N-Queens

N-Queens is the classic introduction to backtracking — building a solution one choice at a time, and undoing a choice the moment it leads to a dead end. It also teaches a beautiful trick for checking diagonals in O(1).

The slow way first

You could try placing queens on every subset of squares and check each board — but there are C(16, 4) boards even for n = 4, and it explodes super fast. Even "one queen per row, any column" gives nⁿ boards. We need to stop exploring a branch as soon as it cannot possibly work.

The idea: place one queen per row, prune early

Since no two queens can share a row, put exactly one queen in each row. Now the only choice per row is which column. We fill rows top to bottom; when we reach a row, we try each column and skip any that is attacked by an already-placed queen.

The diagonal check is the elegant part. Every square on a ↘ diagonal has the same row + col; every square on a ↙ diagonal has the same row - col. So we keep three sets — cols, diag1 (row + col), diag2 (row - col) — and a square is safe iff none of its three keys is in those sets. That makes each safety check O(1).

The whole method is place → recurse → undo. If a row has no safe column, we return and the previous row tries its next column instead.

Walk through it

Step through the animation. We place a queen in row 0 (column 0), then row 1 (column 2). Row 2 turns out to have no safe square — a dead end. We backtrack, lifting the queen off row 1 and freeing its sets, then place it at column 3 instead. From there rows 2 and 3 each find a safe column, and reaching row 4 means the board is full — a complete solution.

Pseudocode

cols, diag1, diag2 = empty sets
place(row):
    if row == n:                       # all rows filled
        return 1                        # one valid board
    count = 0
    for col in 0..n-1:
        if col in cols or row+col in diag1 or row-col in diag2:
            skip this column            # attacked -> prune
        add col, row+col, row-col to the sets
        count += place(row + 1)         # recurse into the next row
        remove them again               # backtrack / undo
    return count

The Python solution

def solve(n):
    cols, diag1, diag2 = set(), set(), set()
    def place(row):
        if row == n:
            return 1            # a full board -> one solution
        count = 0
        for col in range(n):
            if col in cols or (row + col) in diag1 or (row - col) in diag2:
                continue        # attacked -> prune
            cols.add(col); diag1.add(row + col); diag2.add(row - col)
            count += place(row + 1)
            cols.discard(col); diag1.discard(row + col); diag2.discard(row - col)
        return count
    return place(0)

• cols, diag1, diag2 track the columns and the two diagonal families that are already under attack.
• Line 8 is the pruning test — row + col keys the ↘ diagonals, row - col keys the ↙ diagonals, so each is an O(1) set lookup.
• Lines 10–12 are the heart of backtracking: add the queen’s keys, recurse into the next row, then discard them so the next iteration starts from a clean slate.
• Reaching row == n (line 4) means every row holds a non-conflicting queen — one complete solution.

Complexity

The n! bound is loose — pruning cuts the real work far below it. Space is O(n): the recursion goes n deep and the three sets hold at most n keys each.

When this pattern shows up

Practice