LeetCode 51 · Backtracking

N-Queens, explained with a picture

Placing queens that can’t attack each other.

HardBacktracking
▶ Watch it step by step

The problem

Place n chess queens on an n × n board so that no two attack each other (no shared row, column or diagonal). Return all solutions.

Input:  n = 4
Output: 2 solutions (queens in columns [1,3,0,2] and [2,0,3,1], one per row)

Picture it

Picture a chessboard. We place one queen per row, from top to bottom. In each row we try every column that is not attacked by queens already placed (same column, or either diagonal). If a row has no safe column, we go back up and move the previous queen.

How to recognise it

  • You must place items on a board so that no two conflict, and return all valid placements.
  • The rules are of the form "nothing shares a row, column or diagonal", so placing one item rules out many squares for later ones.
  • The board is small (n up to 9), which allows an exponential search, but 9^9 ≈ 387 million arrangements is already too many to test one by one.
  • Because each queen needs its own row, the natural decision tree has one level per row and up to n branches (the columns).
  • Place, recurse, remove: this is the textbook form of backtracking, where conflicts let you abandon a branch long before the board is full.

Start with brute force

Put one queen in every row (there must be exactly one per row), try every combination of columns, and test the finished board for conflicts.

from itertools import product

def solve_n_queens_brute(n):
    res = []
    for cols in product(range(n), repeat=n):         # cols[r] = column in row r
        if (len(set(cols)) == n
                and len({r - c for r, c in enumerate(cols)}) == n
                and len({r + c for r, c in enumerate(cols)}) == n):
            res.append(list(cols))
    return res

There are n^n candidate boards: 4^4 = 256, 8^8 = 16,777,216, 9^9 = 387,420,489. Each is checked only after it is complete, so a board with two queens in the same column is built in full before being rejected. Time is O(n · n^n) and space is O(n) beyond the output.

From brute force to the idea

  1. Place row by row. place(r) puts a queen in row r, trying each column c. A queen in each row guarantees no two share a row.
  2. Know what is attacked in O(1). Keep three sets: cols (columns taken), d1 (the values r - c, which are equal along a diagonal running down and to the right) and d2 (the values r + c, equal along a diagonal running down and to the left).
  3. Skip attacked squares. If c in cols or r - c in d1 or r + c in d2, the square is attacked, so continue.
  4. Choose, recurse, un-choose. Add c to all three sets and append it to board, call place(r + 1), then remove c from all three and pop it.
  5. Save at the bottom. When r == n every row has a queen, so board (the column of each row) is a solution. The code turns it into LeetCode's strings, one per row: "Q" in the queen's column and "." everywhere else.

This is the key idea: the three sets reject an attacked square in O(1), so bad branches die early. For n = 8 the shown code makes about 2,000 calls, against 16.8 million boards for the brute force.

The key idea

Backtrack row by row; three sets (columns, r−c diagonals, r+c diagonals) make each safety check O(1).

Python solution

def solve_n_queens(n):
    cols, d1, d2, res, board = set(), set(), set(), [], []
    def place(r):
        if r == n:
            res.append(["." * c + "Q" + "." * (n - c - 1) for c in board]); return
        for c in range(n):
            if c in cols or r - c in d1 or r + c in d2:
                continue                  # attacked: skip this square
            cols.add(c); d1.add(r - c); d2.add(r + c); board.append(c)
            place(r + 1)
            cols.remove(c); d1.remove(r - c); d2.remove(r + c); board.pop()
    place(0)
    return res

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute force (all n^n boards)O(n · n^n)O(n) beyond the output
Row by row with three sets (shown code)Bounded by O(n!) because each row uses a column no earlier row used; in practice far less because diagonals prune tooO(n): the three sets, board and the recursion are each at most n deep

Edge cases

  • n = 1: returns [[0]], a single queen at column 0.
  • n = 2 and n = 3: return []; no placement works.
  • n = 4: returns [[1, 3, 0, 2], [2, 0, 3, 1]], the two solutions in the example, each listed as the column of the queen in rows 0 to 3.
  • n = 8: 92 solutions. n = 9: 352 solutions.
  • Output format: each solution is a list of strings such as ".Q..", as LeetCode expects. The comprehension builds new strings, so later changes to board cannot affect saved answers.
  • Sets are shared: the three sets and board are updated in place and restored after every call, so they are empty again when solve_n_queens returns.

Common mistakes

  • Checking only the columns. That accepts every arrangement with one queen per row and column, which for n = 4 is all 24 permutations.
  • Using one diagonal set for both directions, so r - c and r + c values collide.
  • Forgetting to remove an entry from one of the three sets after the recursive call. The set then keeps "attacked" marks from dead branches. Forgetting only the r + c set returns 0 solutions for n = 4.
  • Saving board itself (for example res.append(board)) instead of a converted copy, which makes every answer the same list that is emptied by the time the search ends.
Your turn: only count the solutions

Return how many solutions exist for n (for example 92 for n = 8), without keeping the boards. Describe your approach, then write it if you like.

Compare with our answer

Use the same row by row search with the same three sets, but return numbers instead of collecting boards: a full board counts 1, and each call returns the sum of what its children return. There is no need to keep board or a result list.

def count_queens(n):
    cols, d1, d2 = set(), set(), set()
    def place(r):
        if r == n:
            return 1
        total = 0
        for c in range(n):
            if c in cols or r - c in d1 or r + c in d2:
                continue
            cols.add(c); d1.add(r - c); d2.add(r + c)
            total += place(r + 1)
            cols.remove(c); d1.remove(r - c); d2.remove(r + c)
        return total
    return place(0)

The counts for n = 1 to 10 are 1, 0, 0, 2, 10, 4, 40, 92, 352, 724. The time is the same as for the full version, but space is O(n) with no output at all.

A strong answer mentions: returning a count from each call, adding a full board as 1, and keeping the same three sets and the same undo steps.

Check what stuck

1. A seating planner must list every way to place 6 guests in 6 rows so that no two guests share a column or a diagonal. Which approach fits best?

2. Why do the sets use r - c for one diagonal and r + c for the other?

3. A learner deletes d2.remove(r + c) but keeps the other removals. Which input exposes the bug?

Score 60% or more and the lesson is marked complete.