N-Queens: Constraint Backtracking

Place n queens on an n x n chessboard so that no two queens attack each other. Return all distinct solutions, where each solution is a board configuration with queen positions.

This is LeetCode 51: N-Queens, and it is the classic constraint satisfaction problem that comes up in every algorithms course. If Subsets is the "hello world" of backtracking and Word Search is backtracking on a grid, N-Queens is where backtracking meets constraint validation. You are not just exploring choices. You are pruning entire branches the moment a constraint is violated.

Why this problem matters

N-Queens teaches you how to combine the choose-explore-unchoose template with efficient constraint checking. In simpler backtracking problems, any choice is valid and you just enumerate. Here, most choices are invalid, and the whole point is to detect that early and skip them. That skill transfers directly to Sudoku solvers, graph coloring, scheduling problems, and any interview question where you need to "find all valid configurations."

The N-Queens LeetCode problem also forces you to think about how to represent constraints compactly. A naive approach checks the entire board for queen conflicts at every step. The elegant approach uses three sets to track columns and diagonals, turning each constraint check into an O(1) lookup. That optimization is the kind of thing interviewers love to see.

The key insight

Since each row must contain exactly one queen, you can place queens row by row. At row r, you try every column c from 0 to n-1. The question is: does column c conflict with any queen already placed?

A queen attacks along its row, column, and both diagonals. We already handle rows by construction (one queen per row). That leaves three constraints to check:

1. Column: is column c already taken?
2. Main diagonal (top-left to bottom-right): is this diagonal already taken?
3. Anti-diagonal (top-right to bottom-left): is this diagonal already taken?

Here is the diagonal trick that makes this fast. Every cell on the same main diagonal shares the same value of row - col. Every cell on the same anti-diagonal shares the same value of row + col. Think about it: if you move one step down and one step right along a main diagonal, row increases by 1 and col increases by 1, so row - col stays constant. For the anti-diagonal, moving one step down and one step left means row increases by 1 and col decreases by 1, so row + col stays constant.

That means you can track all three constraints with three sets:

• cols: set of occupied column indices
• diags: set of occupied row - col values
• anti_diags: set of occupied row + col values

Before placing a queen at (r, c), check whether c is in cols, r - c is in diags, or r + c is in anti_diags. If any of those is true, skip this column. If all are clear, place the queen and add the values to the sets.

The backtracking solution

def solve_n_queens(n: int) -> list[list[str]]:
    result = []
    board = [["."] * n for _ in range(n)]
    cols = set()
    diags = set()        # row - col
    anti_diags = set()   # row + col

    def backtrack(row):
        if row == n:
            # All queens placed, record the board
            result.append(["".join(r) for r in board])
            return

        for col in range(n):
            # Constraint check
            if col in cols:
                continue
            if row - col in diags:
                continue
            if row + col in anti_diags:
                continue

            # Choose: place queen
            board[row][col] = "Q"
            cols.add(col)
            diags.add(row - col)
            anti_diags.add(row + col)

            # Explore: move to next row
            backtrack(row + 1)

            # Unchoose: remove queen
            board[row][col] = "."
            cols.remove(col)
            diags.remove(row - col)
            anti_diags.remove(row + col)

    backtrack(0)
    return result

Let's break this down.

The outer function sets up the empty board and the three constraint sets, then calls backtrack(0) to start placing queens from row 0.

Inside backtrack, the base case is row == n. When we have successfully placed a queen in every row, we have a complete solution. We convert the board to strings and add it to result.

The for loop tries each column in the current row. For each column, we check the three constraints. If any constraint is violated, we continue to the next column. This is where the pruning happens. Instead of exploring a subtree that is guaranteed to fail, we skip it entirely.

If all constraints pass, we place the queen (choose), update the three sets, and recurse to the next row (explore). When the recursive call returns, we undo everything (unchoose): remove the queen from the board and remove the values from the constraint sets. This restores the state so we can try the next column.

The continue statements are the constraint validation building block. They act as a filter at the top of the loop body, rejecting invalid choices before we commit to them. Without these checks, we would explore every possible arrangement of n queens and only validate at the end. With them, we cut off invalid branches immediately.

Visual walkthrough

Let's trace the algorithm on a 4x4 board. Watch how constraint violations trigger backtracking, and how the diagonal sets catch conflicts that a column-only check would miss.

The key moment is Step 4. After placing queens at (0,0) and (1,2), every column in row 2 is blocked by either a column constraint or a diagonal constraint. There is no valid move, so we backtrack and try a different column in row 1. This pruning is what keeps the algorithm from wasting time exploring dead-end configurations.

The diagonal trick explained

This deserves its own section because it is the part people forget.

Picture a 4x4 grid with coordinates:

(0,0) (0,1) (0,2) (0,3)
(1,0) (1,1) (1,2) (1,3)
(2,0) (2,1) (2,2) (2,3)
(3,0) (3,1) (3,2) (3,3)

Now compute row - col for every cell:

 0   -1   -2   -3
 1    0   -1   -2
 2    1    0   -1
 3    2    1    0

See the diagonals? All cells with row - col = 0 sit on the main diagonal: (0,0), (1,1), (2,2), (3,3). All cells with row - col = -1 sit on the diagonal one step to the right: (0,1), (1,2), (2,3). If a queen sits at (0,0), then row - col = 0 goes into the diags set. When we later consider (1,1), we compute 1 - 1 = 0, find it in diags, and reject it immediately.

Now compute row + col:

 0    1    2    3
 1    2    3    4
 2    3    4    5
 3    4    5    6

The anti-diagonals show up: (0,3), (1,2), (2,1), (3,0) all have row + col = 3. A queen at (0,3) blocks all of them.

Two formulas. Two sets. O(1) checks. That is the entire diagonal story.

Complexity analysis

Time is hard to pin down exactly, but it is roughly O(n!). At row 0 you have n column choices. At row 1, constraint pruning eliminates at least 1 column (the one taken in row 0), leaving at most n-1 choices. At row 2, at most n-2, and so on. That gives an upper bound of n!. In practice, diagonal constraints prune far more aggressively, so the real number of nodes explored is much smaller than n!. But n! is the standard answer for interviews.

Space is O(n^2) for the board itself. The three constraint sets use O(n) each. The recursion stack goes n levels deep, using O(n) space. If we count the output, there can be many solutions (for n = 8 there are 92), each of size O(n^2). But ignoring output storage, the working space is O(n^2).

Edge cases

Before submitting, check these:

• n = 1: the only solution is a single queen on a 1x1 board. Should return [["Q"]].
• n = 2 and n = 3: no valid solutions exist. Should return [].
• n = 4: exactly 2 solutions. Good test case for verifying your diagonal logic.
• n = 8: the classic version. 92 solutions. If your algorithm is too slow here, you probably forgot the constraint pruning and are brute-forcing all arrangements.

The building blocks

This problem is built on two reusable pieces that CodeBricks drills independently.

1. Constraint validation

The pattern of checking constraints before committing to a choice:

for candidate in choices:
    if violates_constraint(candidate):
        continue  # prune this branch

    apply(candidate)
    explore()
    undo(candidate)

In N-Queens, the constraints are the three set lookups. In Sudoku, the constraints check row, column, and 3x3 box. In graph coloring, the constraint checks neighboring node colors. The shape is always the same: a guard clause at the top of the loop that skips invalid candidates.

This is different from unconstrained backtracking like Subsets, where every choice is valid and you just enumerate. In constrained backtracking, the constraint check is what makes the algorithm fast enough to be practical. Without it, you are doing brute-force enumeration, which is exponentially slower.

2. Choose-explore-unchoose (backtracking template)

The same skeleton from Word Search and Subsets:

def backtrack(state):
    if is_solution(state):
        record(state)
        return

    for choice in candidates(state):
        make_choice(choice)      # choose
        backtrack(state)          # explore
        undo_choice(choice)       # unchoose

In N-Queens, make_choice is placing the queen and updating three sets. undo_choice is removing the queen and deleting from the sets. The "candidates" loop iterates over columns 0 to n-1 in the current row. The constraint validation filters out invalid candidates before make_choice runs.

The combination of choose-explore-unchoose with constraint pruning is what makes N-Queens a constraint satisfaction problem rather than a pure enumeration problem. You are not generating all possible queen placements and filtering afterward. You are filtering as you go, cutting off entire subtrees the moment a constraint fails.

Common mistakes

1. Forgetting the diagonal constraints entirely. If you only check columns, you will get configurations where queens share a diagonal. The output will have too many "solutions" and most of them will be invalid.

2. Mixing up row - col and row + col. Both are needed. One tracks main diagonals, the other tracks anti-diagonals. If you only use one, you miss half the diagonal conflicts.

3. Not undoing all state in the unchoose step. You need to remove from cols, diags, and anti_diags, and reset the board cell. Missing any one of these corrupts the state for sibling branches.

4. Checking constraints after placing the queen. The constraint check should happen before you modify the board and sets. If you place first and check second, you need to undo on failure, which is messier and error-prone. The continue-before-modify pattern is cleaner.

5. Using O(n) diagonal checks instead of sets. Walking the diagonal to check for conflicts works but makes each placement O(n) instead of O(1). For n up to 9 (the LeetCode constraint), it still passes, but using sets is the approach interviewers expect and the one worth memorizing.

When to use this pattern

Look for these signals:

• The problem asks for all valid configurations under constraints
• You need to place items such that no two violate a rule (rows, columns, diagonals, adjacency)
• The problem has a "one per row" or "one per group" structure that lets you recurse level by level
• Constraints can be checked incrementally (you can validate as you build, not just at the end)

Problems that use the same constrained backtracking pattern:

• N-Queens II (LeetCode 52): same approach, but just count solutions instead of building boards
• Sudoku Solver (LeetCode 37): constrained backtracking with row, column, and box sets
• Combination Sum (LeetCode 39): backtracking with a running sum constraint
• Permutations (LeetCode 46): backtracking where the constraint is "element not yet used"

From understanding to recall

You understand how the three sets track constraints. You see how row - col and row + col map to diagonals, and how the choose-explore-unchoose skeleton drives the search. But can you write the constraint validation and diagonal tracking from scratch in an interview?

That is the hard part. The N-Queens LeetCode solution has specific details that are easy to mix up under pressure: which formula is the main diagonal vs. the anti-diagonal, remembering to undo all three sets, checking constraints before placing. These are not conceptual issues. They are recall problems.

Spaced repetition fixes recall. You practice writing the constraint validation guard clause and the diagonal set updates from memory at increasing intervals. After a few rounds, the pattern is automatic. You see "N-Queens" or "place items with constraints" and the code flows out without hesitation.

The constraint-validation and choose-explore-unchoose patterns are two of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Subsets - The simplest backtracking problem. Compare it to N-Queens to see what changes when you add constraints to the choose-explore-unchoose template.
• Word Search - Grid backtracking with the same choose-explore-unchoose skeleton. N-Queens adds constraint sets; Word Search adds grid neighbor generation.
• Permutations - Backtracking where every element must be used. A good contrast to N-Queens, where constraint validation prunes most branches.

CodeBricks breaks N-Queens into its constraint-validation and choose-explore-unchoose building blocks, then drills them independently with spaced repetition. You type the backtracking constraints from scratch until the pattern is automatic. When a constraint satisfaction problem shows up in your interview, you do not think about it. You just write it.