N-Queens and Classic Backtracking Problems

Backtracking is a way of solving problems by trying a choice, recursing to see if that choice leads to a full solution, and undoing the choice if it doesn’t — then trying the next option. It is how you brute-force your way through a search space without actually visiting every possible combination, because bad partial choices get abandoned early. The N-Queens problem is the textbook example: place N chess queens on an N×N board so that no two attack each other. It is small enough to reason about by hand yet rich enough to show every feature of backtracking, which is why it shows up constantly in interviews and algorithms courses.

Overview: How Backtracking Works

Picture seating N people at a long table, one per row, where certain pairs of people cannot sit in ways that create a conflict. You seat person 1, then try to seat person 2 in the first available seat that doesn’t conflict with person 1. If person 2 has no valid seat at all, you don’t give up on the whole table — you go back and move person 1 to a different seat and try again. That “try, recurse, undo” loop is backtracking in its entirety.

In N-Queens, a queen attacks any square in its own row, its own column, or either diagonal. A clever observation simplifies the search enormously: since no two queens can share a row, we can place exactly one queen per row and only decide which column each row’s queen goes in. That turns the problem into choosing a sequence of column indices, one per row, such that no two chosen columns are equal (no column conflict) and no two differ by the same amount as their row distance (no diagonal conflict, since a diagonal step changes row and column by the same amount).

The algorithm walks through rows 0 to N-1. For the current row, it tries every column 0 to N-1. If a column is safe given the queens already placed in earlier rows, it places the queen there and recurses into the next row. If that recursive call fails to complete the board, the queen is removed (backtracked) and the next column is tried. If every column fails, the function returns to the previous row, which then tries its next option. When a row index reaches N, every row has a queen and a full solution has been found.

The undo step is the entire idea — without it, a choice made deep in the recursion would leak into unrelated branches of the search tree, corrupting every solution found afterward. This is the single most important habit to get right in any backtracking function.

Time and Space Complexity

Aspect	Complexity	Why
N-Queens search, worst case	O(N!)	Row 0 has N column choices, row 1 has at most N-1 remaining (a column can’t repeat), row 2 at most N-2, and so on — bounding the search tree by N! even before diagonal pruning removes many branches in practice.
Safety check per placement	O(N)	is_safe compares the candidate column against every queen already placed, and up to N queens can already be on the board.
Total work, worst case	O(N × N!)	Each of the up-to-N! nodes in the search tree does an O(N) safety check.
Recursion stack depth	O(N)	The recursion goes exactly one call deep per row, and there are N rows.
Storing all S solutions	O(S × N)	Each solution is a list of N column indices, and there are S solutions found.
Generic backtracking (subsets)	O(2^N) time, O(N) stack	Every element is either included or excluded, giving 2^N possible subsets; the recursion depth never exceeds the number of elements.

Backtracking algorithms are exponential in the worst case — there is no way around that, since the problems they solve (constraint satisfaction, combinatorial search) are inherently about exploring a search space that grows exponentially with input size. The value of backtracking over brute force is that pruning (the is_safe check) cuts off huge subtrees early, so the actual runtime is almost always far smaller than the theoretical worst case.

Examples

Example 1: Solving 4-Queens and counting solutions

def solve_n_queens(n: int) -> list[list[int]]:
    solutions: list[list[int]] = []
    placement: list[int] = []

    def is_safe(row: int, col: int) -> bool:
        for prev_row, prev_col in enumerate(placement):
            if prev_col == col:
                return False
            if abs(prev_col - col) == abs(prev_row - row):
                return False
        return True

    def backtrack(row: int) -> None:
        if row == n:
            solutions.append(placement.copy())
            return
        for col in range(n):
            if is_safe(row, col):
                placement.append(col)
                backtrack(row + 1)
                placement.pop()

    backtrack(0)
    return solutions


def main() -> None:
    n = 4
    solutions = solve_n_queens(n)
    print(f"Number of solutions for {n}-queens: {len(solutions)}")
    for solution in solutions:
        print(solution)


main()

Output:

Number of solutions for 4-queens: 2
[1, 3, 0, 2]
[2, 0, 3, 1]

Each returned list is a compact board encoding: index i is the row, and the value at that index is the column holding row i‘s queen. [1, 3, 0, 2] means row 0’s queen is in column 1, row 1’s in column 3, row 2’s in column 0, and row 3’s in column 2 — and indeed 4-Queens has exactly two solutions, which are mirror images of each other.

Example 2: Visualizing a board and scaling to 8-Queens

def solve_n_queens(n: int) -> list[list[int]]:
    solutions: list[list[int]] = []
    placement: list[int] = []

    def is_safe(row: int, col: int) -> bool:
        for prev_row, prev_col in enumerate(placement):
            if prev_col == col:
                return False
            if abs(prev_col - col) == abs(prev_row - row):
                return False
        return True

    def backtrack(row: int) -> None:
        if row == n:
            solutions.append(placement.copy())
            return
        for col in range(n):
            if is_safe(row, col):
                placement.append(col)
                backtrack(row + 1)
                placement.pop()

    backtrack(0)
    return solutions


def print_board(solution: list[int]) -> None:
    n = len(solution)
    for row in range(n):
        line = ""
        for col in range(n):
            line += "Q " if solution[row] == col else ". "
        print(line.rstrip())


def main() -> None:
    four_queens_solutions = solve_n_queens(4)
    print_board(four_queens_solutions[0])
    print()
    eight_queens_solutions = solve_n_queens(8)
    print(f"8-queens has {len(eight_queens_solutions)} solutions")


main()

Output:

. Q . .
. . . Q
Q . . .
. . Q .

8-queens has 92 solutions

The board print confirms the first 4-Queens solution visually, and the same untouched solve_n_queens function scales straight up to the classic 8×8 board, correctly finding all 92 solutions with no changes to the algorithm — only N changed.

Example 3: The same pattern applied to subsets

def generate_subsets(nums: list[int]) -> list[list[int]]:
    subsets: list[list[int]] = []
    current: list[int] = []

    def backtrack(start: int) -> None:
        subsets.append(current.copy())
        for i in range(start, len(nums)):
            current.append(nums[i])
            backtrack(i + 1)
            current.pop()

    backtrack(0)
    return subsets


def main() -> None:
    nums = [1, 2, 3]
    subsets = generate_subsets(nums)
    print(f"Total subsets: {len(subsets)}")
    for subset in subsets:
        print(subset)


main()

Output:

Total subsets: 8
[]
[1]
[1, 2]
[1, 2, 3]
[1, 3]
[2]
[2, 3]
[3]

Notice the shape is identical to N-Queens: a running partial answer (current instead of placement), a loop over choices, a recursive call, and an undo (current.pop()). Only the “is this choice valid?” check and the “record a full answer” condition change between problems — this is the reusable backtracking template.

How It Works Step by Step

Trace solve_n_queens(4) by hand to see the search-and-undo in action:

• Row 0: try column 0. No queens yet, so it’s safe. Place queen at (0, 0).
• Row 1: column 0 is taken (same column). Column 1 is diagonally adjacent to (0,0) (column distance 1 equals row distance 1) — unsafe. Column 2 is safe. Place queen at (1, 2).
• Row 2: column 0 is taken. Column 1 is diagonal to (1,2). Column 2 is taken. Column 3 is diagonal to (1,2). No column works — backtrack: remove the queen from (1, 2) and try row 1’s next column.
• Row 1: column 3 is safe relative to (0,0). Place queen at (1, 3). Row 2 now finds column 1 safe, and row 3 finds every column blocked — another dead end, so row 2 and then row 1 backtrack all the way out, exhausting row 0’s column 0 entirely.
• Row 0: backtrack to column 1. This branch, followed the same way, eventually places queens at (0,1), (1,3), (2,0), (3,2) — a complete board, i.e. the first solution: [1, 3, 0, 2].
• The search doesn’t stop there: it keeps backtracking and trying remaining columns at every row, eventually also discovering [2, 0, 3, 1] before every branch from row 0 is exhausted, at which point the function returns both solutions.

The key insight from this trace: the algorithm never “knows” in advance that column 0 in row 0 is a dead end for most branches. It discovers that by recursing forward until it gets stuck, then walking back one step at a time, undoing exactly the choices that led nowhere — not the entire search.

Common Mistakes

Mistake 1: forgetting to undo the choice

The single most common backtracking bug is placing a queen (or including an element) and never removing it after the recursive call returns. The board state then leaks between branches that should be independent.

def backtrack(row, n, placement, solutions):
    if row == n:
        solutions.append(placement.copy())
        return
    for col in range(n):
        if is_safe(row, col, placement):
            placement.append(col)
            backtrack(row + 1, n, placement, solutions)
            # BUG: no placement.pop() here -- the choice is never undone,
            # so later branches see leftover queens from earlier branches.

Without the pop, by the time the loop tries its second column, placement still contains the queen from the first (failed) attempt, so is_safe checks against a board that no longer reflects reality. The fix is to always pair every state-changing step with its inverse, right after the recursive call:

for col in range(n):
    if is_safe(row, col, placement):
        placement.append(col)
        backtrack(row + 1, n, placement, solutions)
        placement.pop()  # always undo the choice before trying the next column

Mistake 2: a mutable default argument as the accumulator

It’s tempting to give a helper function a default empty list to accumulate into, but Python creates default argument objects once, when the function is defined — not once per call.

def generate_subsets(nums, start=0, current=[]):
    result = [current[:]]
    for i in range(start, len(nums)):
        current.append(nums[i])
        result.extend(generate_subsets(nums, i + 1, current))
        current.pop()
    return result
# current=[] is created ONCE, when the function is defined, and reused
# across every call -- unrelated calls can see leftover state.

Any two separate calls to generate_subsets without an explicit current argument would share the exact same list object, so state from one call can bleed into a completely unrelated call. The fix is the standard Python idiom: default to None and create a fresh list inside the function body.

def generate_subsets(nums: list[int], start: int = 0, current: list[int] | None = None) -> list[list[int]]:
    if current is None:
        current = []
    result = [current[:]]
    for i in range(start, len(nums)):
        current.append(nums[i])
        result.extend(generate_subsets(nums, i + 1, current))
        current.pop()
    return result

Best Practices

• Always pair a state-changing line (append, setting a grid cell, marking visited) with its exact inverse right after the recursive call — write the undo at the same time you write the choice, not as an afterthought.
• Push the validity check (is_safe) as early as possible in the loop, before recursing, so invalid branches are pruned immediately instead of being discovered one level deeper.
• Prefer copying only when you record a full solution (placement.copy()), not on every recursive call — mutating one shared list and copying only at success points is far cheaper than passing around new lists.
• Represent a row-by-row constraint problem (queens, Sudoku rows) with a flat list indexed by row, not a full 2D grid, when possible — it’s both faster to check and simpler to reason about.
• Never default a mutable argument to a list, dict, or set; use None and initialize inside the function body instead.
• Reach for backtracking when a problem asks for all solutions, any valid solution under constraints, or a count of arrangements — and reach for dynamic programming instead when the same subproblems repeat and you only need an optimal value, since backtracking alone re-explores overlapping states.

Practice Exercises

• Count without storing. Modify solve_n_queens so it returns only the number of solutions as an integer, without ever building a list of boards. This keeps memory at O(N) instead of O(S × N). Hint: use a single counter variable in the enclosing scope instead of appending to a list.
• Permutations from scratch. Write generate_permutations(nums: list[int]) -> list[list[int]] using backtracking with a used set to track which elements are already placed. For input [1, 2, 3] you should get exactly 6 permutations.
• Small boards, by hand. Run your N-Queens solver for N = 1, N = 2, N = 3, and N = 6, and confirm the solution counts are 1, 0, 0, and 4 respectively. Try to explain on paper why 2-Queens and 3-Queens have no solutions at all before running the code.

Summary

• Backtracking tries a choice, recurses, and undoes the choice if it doesn’t pan out — the undo step is what makes it correct, not optional cleanup.
• N-Queens places one queen per row and searches for a safe column per row, pruning with an O(N) safety check against columns and diagonals.
• Worst-case time is O(N!) for the search tree (O(N × N!) counting safety checks); space is O(N) for the recursion stack and current placement, plus O(S × N) if every solution is stored.
• The same append → recurse → pop template solves subsets (O(2^N)), permutations, and many other classic “generate all valid arrangements” problems — only the validity check and success condition change.
• The two most common bugs are forgetting to undo a state change and using a mutable default argument as an accumulator — both corrupt state across branches that should be independent.