N queens explained: how does backtracking solve it?

In this article

1. Before you start
2. Why interviewers ask this
3. N-queens from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

The problem belongs to the pattern family covered in coding interview questions: the patterns, the method and how to practise.

Why interviewers ask this

The n-queens problem tests whether you can search a huge space of choices without looking at all of it. A candidate who only knows brute force checks every arrangement. A candidate who understands backtracking stops a half-built board as soon as it breaks a rule.

The public LeetCode statement asks for all distinct solutions for a given n and limits n to 9 or less. A small limit like this is typical when the output grows quickly.

A weak answer says "try everything and check." A strong answer says "one queen per row, three sets for conflicts, undo on the way back." A Staff-level answer adds why the time bound is only an upper bound, and when a different method suits a very large board.

N-queens from first principles

N-queens problem

The n-queens problem is a puzzle that asks you to place n chess queens on an n-by-n board so that no two queens share a row, a column or a diagonal, and to find one or all such placements.

Anti-diagonal

An anti-diagonal is a line of squares running from top right to bottom left, where every square has the same value of row plus column.

In plain words

A queen attacks along its row, its column and both diagonals. Two queens clash if they share any of those lines.

The analogy is seating guests at a table. You seat one person at a time. If someone would sit next to an enemy, you pick another seat. If no seat works, you ask the last person to move. The analogy breaks in one place: the board is a grid, so one seat blocks four kinds of lines at once.

In one precise sentence, a solution is a choice of one column for every row such that no column repeats and no two queens share a diagonal. Wikipedia states the rule as no two queens sharing a row, column or diagonal.

Step 1: One queen per row makes a solution a list

One queen per row means a solution is a list of columns. Two queens in one row would already attack each other, and a board with n queens and n rows therefore has exactly one queen in each row.

So the code never stores a grid. It stores board[r], the column of the queen in row r. Row 0 is chosen first, then row 1, and so on.

Input: the board size n. Output: an empty list that will hold one column per row. You now know the shape of the answer, and the search only has to choose a column for each row in turn. This single idea removes every board with two queens in a row from the search before it starts.

Step 2: Three sets test a square in constant time

Three sets track the three kinds of line a new queen could clash with. One set holds used columns. One holds the difference row minus column, which is constant along a diagonal. One holds the sum row plus column, which is constant along an anti-diagonal. The Oxford thesis on the problem states the same diagonal condition: two queens do not attack diagonally exactly when their row-plus-column and row-minus-column values differ.

A square is safe if its column, its difference and its sum are all missing from the sets. That is a constant-time check, written O(1). A secondary tutorial notes that scanning all earlier queens costs O(n) per check, so the three sets make it O(1).

For n = 8 the difference runs from -7 to 7, which is 15 values, and the sum from 0 to 14, which is 15 values.¹ The difference can be negative, so use a set (as the code below does) or add an offset when you use arrays.

Step 3: Place, recurse, undo

Place, recurse, undo is the heart of backtracking. For a row, try each column in turn. Skip a column whose square is attacked. Otherwise add the column, the difference and the sum to the sets, append the column to the list, and call the same function for the next row.

When that call returns, remove everything you added. Undo the placement even if the recursive call found a solution, because the next column of this row must start from a board without your queen.

Forgetting this step is the classic error. The tutorial's own warning says to remove the column and both diagonals after the recursive call, or later branches see phantom queens. A phantom queen blocks squares that are really free, so the code misses valid solutions and may report none.

Input: the row number. Output: the sets and the list exactly as they were before the call. This is also why the function is correct: every call leaves the state unchanged.

Step 4: Record a solution when every row is filled

A solution is recorded when the row number equals n. At that point every row holds a queen, and the rules were checked at each placement, so the board is valid.

Copy the list before saving it, because the same list keeps changing as the search continues. Then return, so the caller can undo its own placement.

Rows that run out of safe squares simply return without recording anything. That is a dead end, and the undo in Step 3 sends the search back to try the previous row's next column. Here is the whole function in Python:

def solve_n_queens(n):
    cols, diag, anti = set(), set(), set()
    board = []            # board[r] = column of the queen in row r
    solutions = []

    def place(r):
        if r == n:
            solutions.append(board[:])   # copy, the list keeps changing
            return
        for c in range(n):
            if c in cols or (r - c) in diag or (r + c) in anti:
                continue
            cols.add(c); diag.add(r - c); anti.add(r + c)
            board.append(c)
            place(r + 1)
            board.pop()                  # undo
            cols.remove(c); diag.remove(r - c); anti.remove(r + c)

    place(0)
    return solutions

The function name is solve_n_queens and the inner function is place. Calling solve_n_queens(4) returns two boards.¹

1 · One queen per row2 · Three sets3 · Place, recurse, undo4 · Record a solutionReplay

Step-by-step description

1. A solution is a list of columns.
2. Columns and both diagonals are tracked.
3. Every placement is undone after the call.
4. A full row count records one solution.

• One queen per row means a solution is a list of columns.
• Three sets track columns and both diagonals.
• Undo the placement after each recursive call.
• A full row count means one solution is recorded.

The four steps in the figure follow the sections above. One queen per row means a solution is a list of columns. Three sets track columns and both diagonals. Undo the placement after each recursive call. A full row count means one solution is recorded.

Worked example

The 4-queens board has two solutions, shown on the problem statement as .Q.., ...Q, Q..., ..Q. and ..Q., Q..., ...Q, .Q... As lists of columns, counting from 0, they are [1, 3, 0, 2] and [2, 0, 3, 1].¹ The Wikipedia article counts the two as one fundamental solution. A fundamental solution is one group of boards that match after rotation or reflection.

Trace the search for n = 4. Row 0 tries column 0 first. Row 1 cannot use column 0 or column 1: column 0 shares the column of the queen at row 0, column 0, and column 1 has the same row-minus-column value, 0, so it sits on her diagonal. Row 1 takes column 2, and then row 2 has no safe square: that is a dead end, so the code undoes column 2 and tries column 3 in row 1.

Row 2 then takes column 1, and row 3 has no safe square, so the code undoes again. Two dead ends from column 0 force the search back to row 0. Row 0 moves to column 1 and finds the solution [1, 3, 0, 2]. The mirror image starts at column 2 and finds [2, 0, 3, 1].

The figure writes each state of that search as one row of a table, so a dead end appears as a row with no safe square.

1 · Start at column 02 · First dead end3 · Second dead end4 · Back to row 05 · SolutionReplay

Step-by-step description

1. Row 0 takes column 0.
2. Row 1 takes column 2 and row 2 has no safe square.
3. After the undo, row 1 takes column 3, row 2 column 1, and row 3 has no safe square.
4. Column 0 is abandoned and row 0 tries column 1.
5. The columns 1, 3, 0, 2 fill every row.

• Row 1 cannot use column 0 or column 1 when row 0 holds column 0.
• Two dead ends from column 0 force the search back to row 0.
• Row 0 moves to column 1 and finds the solution [1, 3, 0, 2].

In total the search places 16 queens, counting every placement that is later undone, and reaches a row with no safe square 4 times.¹

The first number is the count of ways to pick 8 squares from 64, reported in the Wikipedia article; the second is 8 to the power 8 and the third is 8 factorial.¹ Backtracking goes further than permutations, because it drops a partial board at the first clash instead of completing it.

The count of 92 treats a rotated or reflected board as a different solution. The Wikipedia article gives 12 fundamental solutions, and the arithmetic is 11 × 8 + 1 × 4 = 92: eleven groups of 8 boards plus one group of 4. A script that groups the 92 boards by rotation and reflection also finds 12 groups.¹

Text description of the diagram

• There are 2 solutions for 4 queens and 92 for 8 queens.
• No closed formula for the number of solutions is known.

There are 2 solutions for 4 queens and 92 for 8 queens. The count for 6 queens is 4, lower than for 5 queens, so growth is not smooth. Larger boards keep growing: 14,200 for n = 12 and 95,815,104 for n = 17, both listed in Online Encyclopedia of Integer Sequences (OEIS) sequence A000170, which the Oxford thesis also cites for the values up to n = 27.² No closed formula for the number of solutions is known, and as of October 2026 the 27 by 27 board is the largest that has been completely counted.²

Trade-offs and edge cases

Backtracking is conventionally quoted as O(n!) time with O(n) extra space, excluding the stored answer. That is a loose bound: at depth k there are at most n!/(n−k)! nodes, and a plain scan of up to n columns per node would give O(n·n!), so O(n!) is the conventional rounding. Treat it as an upper bound: the pruned search tree is much smaller, because every clash cuts a whole branch. The script's count of 16 placements for n = 4 shows pruning at small scale.¹

Edge cases: solutions exist for every n except 2 and 3, so return an empty list for those two.² The recording step also needs a copy of the list, as shown in Step 4.

Other methods trade completeness for speed. For n of 4 or more, one solution can be built with no search at all by an explicit rule. Iterative repair, also called min-conflicts (Minton et al., 1992, doi 10.1016/0004-3702(92)90007-K), starts with a full board and moves queens to reduce clashes. It can handle a board of 1,000,000 queens, but it may fail to find a solution, unlike backtracking.²

Text description of the diagram

• Backtracking is complete and returns every solution.
• Min-conflicts can get stuck at a local optimum.
• Direct construction needs no search for n of 4 or more.

Backtracking is complete and returns every solution. Min-conflicts can get stuck at a local optimum. Direct construction needs no search for n of 4 or more. If some queens are already placed, finding a completion is nondeterministic polynomial-time (NP) complete (Gent et al., 2017), meaning no fast general method is known, so no simple trick replaces the search there.

The same place-recurse-undo shape appears in other problems. Detecting a cycle in a directed graph marks a node while exploring and unmarks it on the way back, and topological sort by depth-first search uses the same on-stack mark to detect a cycle. Other classic coding-round problems use different patterns: the sliding window solution, a heap-based selection problem and prefix sums with a hash map.

How to answer it in an interview

The spoken structure: say the one-queen-per-row idea, name the three sets, describe place-recurse-undo, then state the cost as an upper bound.

Common mistakes

• "A solution exists for every n." (wrong) There is none for n = 2 and n = 3. (right) "I return an empty list for n of 2 or 3."
• "There are 92 genuinely different 8-queens boards." (wrong) The 92 counts rotations and reflections separately. (right) "There are 92 solutions, 12 of them fundamental."
• "I skip the undo because the loop moves on anyway." (wrong) Phantom queens block free squares in later branches. (right) "I remove the column and both diagonals after the recursive call."
• "Backtracking is just brute force." (wrong) Brute force examines every arrangement, backtracking prunes at the first clash. (right) "It abandons a partial board as soon as it breaks a rule."
• "O(n!) is the exact running time." (wrong) It is an upper bound. (right) "O(n!) is an upper bound and pruning makes the real tree smaller."

Follow-up questions

Does an n-queens solution exist for every n?

No. Solutions exist for every n except 2 and 3, and for n of 4 or more one can be constructed without search.²

How many solutions does the 8 queens puzzle have?

It has 92 solutions, or 12 fundamental solutions when rotations and reflections count as the same board.²

What is the time complexity of the n-queens backtracking solution?

The usual bound is O(n!) time and O(n) extra space, but the bound is loose because early clashes cut most branches. If you are asked for a tighter figure, say the true count of search nodes is much lower and measure it.

How do you count n-queens solutions instead of returning them?

Replace the list of boards with a counter and add one when the row number reaches n. Nothing else changes, and you skip copying boards. If the task wants strings such as .Q.., the code above returns column lists, so convert each solution sol with ["." * c + "Q" + "." * (n - c - 1) for c in sol].

Is there a faster way than backtracking for a very large board?

Min-conflicts repair can handle a board of 1,000,000 queens but may fail to find a solution, and direct construction builds one solution for n of 4 or more. Both return one solution, not all of them.

How do you make the n-queens search faster with bitmasks?

Store the used columns, the diagonals and the anti-diagonals as three integers whose bits mark attacked columns. The safe squares of a row are the bits that are clear in all three, found with one bitwise operation. When you move to the next row, shift the diagonal integer one way and the anti-diagonal integer the other. This removes the sets and is the usual answer to the count-only version of the problem.

Sources

1. Eight queens puzzle — Wikipedia (live page, accessed 2026-10-26), 26 Oct 2026
2. N-Queens (problem statement) — LeetCode (accessed 2026-10-26), 26 Oct 2026
3. The n-queens problem (thesis) — University of Oxford Research Archive, Bowtell (accessed 2026-10-26), 26 Oct 2026
4. N-Queens (LeetCode 51): Backtracking With Diagonal Sets — faangprep.com (secondary tutorial, accessed 2026-10-26), 26 Oct 2026
5. A000170: number of ways of placing n nonattacking queens on an n X n board — On-Line Encyclopedia of Integer Sequences (live page, accessed 2026-10-26), 26 Oct 2026
6. Constructions for the Solution of the m Queens Problem (Hoffman, Loessi and Moore) — Mathematics Magazine 42 (1969), 1 Mar 1969
7. Minimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling problems (Minton et al.) — Artificial Intelligence 58 (1992), 1 Dec 1992
8. Complexity of n-Queens Completion (Gent et al.) — Journal of Artificial Intelligence Research (2017), 30 Aug 2017