Algorithm

N-Queens

Backtracking Pattern

N-Queens

Place n queens on an n × n chessboard so that no two attack each other, and return every distinct arrangement.

A queen attacks along its entire row, its entire column, and both diagonals, without limit of distance. So a valid board has at most one queen in any row, any column, and any diagonal.

Each solution is returned as n strings of length n, using 'Q' for a queen and '.' for an empty square. Solutions may be returned in any order, and an empty list is correct when no arrangement exists.

CONSTRAINTS
  • 1 <= n <= 9
  • Exactly n queens must be placed
  • No two queens may share a row, a column, or either diagonal
  • Diagonals extend the full length of the board, not just adjacent squares
  • n = 2 and n = 3 have no solutions at all
EXAMPLE 1
Input: n = 4
Output: 2 solutions: [".Q..","...Q","Q...","..Q."] and ["..Q.","Q...","...Q",".Q.."]
In the first, queens sit at columns 1, 3, 0, 2 for rows 0 to 3. Check the closest pair: rows 0 and 1 hold columns 1 and 3 — different columns, and the row gap of 1 does not equal the column gap of 2, so they miss each other diagonally. The second solution is the mirror image of the first.
EXAMPLE 2
Input: n = 1
Output: 1 solution: ["Q"]
A single queen on a one-square board attacks nothing, since there is nothing else to attack. The smallest valid input, and it does have a solution.
EXAMPLE 3
Input: n = 2
Output: [] — no solutions
Two queens on a 2×2 board must occupy different rows and different columns, which forces them onto a diagonal, where they attack each other. Returning an empty list rather than an error is the required behaviour.
EXAMPLE 4
Input: n = 3
Output: [] — no solutions
Placing a queen in row 0 leaves at most one safe square in row 1, and that choice always leaves row 2 fully attacked. Both n = 2 and n = 3 are impossible, and every larger n has at least one solution.
What should be returned when no arrangement exists?
An empty list. This genuinely occurs at n = 2 and n = 3, so it is not a hypothetical edge case — it is in the test set.
Do reflections and rotations count as separate solutions?
Yes. The two solutions for n = 4 are mirror images of each other and both must be returned. Counting only distinct arrangements up to symmetry is a different and considerably harder problem.
In what format should each solution be returned?
As a list of n strings, each n characters long, with 'Q' marking a queen and '.' an empty square. Internally it is far easier to track just the column chosen for each row and build the strings at the end.
Does a queen attack along the whole diagonal or only adjacent squares?
The whole diagonal, to the edge of the board — same for rows and columns. Checking only neighbouring squares is a misreading that produces many invalid boards.

Place n queens so none attack each other. Key reframe: there are n queens and n rows, so exactly one queen per row. That means the only choice per row is which column. Picking a column per row makes the row rule impossible to break for free — now only columns and the two diagonals need checking.

Diagonals have a neat fingerprint: a ↘ diagonal has constant row - col; a ↗ diagonal has constant row + col. Keep a set of used columns and used diagonals, and a safety check is just three lookups.

The backtracking template

Every problem in this section is the same loop — three beats: choose, explore, un-choose.

python
def backtrack(state):
    if done(state):
        save(state)              # record the finished answer
        return
    for choice in choices(state):    # what can I pick right now?
        if not ok(choice):
            continue                 # prune: skip bad picks early
        apply(choice)                # CHOOSE
        backtrack(next_state)        # EXPLORE
        undo(choice)                 # UN-CHOOSE: put it back

Only four slots change between problems: done, choices, ok (pruning), and how you finish (save every answer, or return True at the first one). Fill those and the problem is solved.

What changes here
- A choice = put this row's queen in column col.
- Choices = columns 0..n-1.
- Done = a queen in every row (row == n) → save the board.
- Prune = skip col if its column, ↘ diagonal, or ↗ diagonal is taken.
python
def solve_n_queens(n):
    res, place = [], []
    cols, diag, anti = set(), set(), set()   # columns, row-col, row+col

    def backtrack(row):
        if row == n:
            res.append(["." * c + "Q" + "." * (n-c-1) for c in place])
            return
        for col in range(n):
            if col in cols or (row-col) in diag or (row+col) in anti:
                continue                                  # PRUNE: attacked
            cols.add(col); diag.add(row-col); anti.add(row+col)   # CHOOSE
            place.append(col)
            backtrack(row + 1)                            # EXPLORE
            place.pop()                                   # UN-CHOOSE
            cols.remove(col); diag.remove(row-col); anti.remove(row+col)

    backtrack(0)
    return res

Undo all the state (column + both diagonals + place) — miss one and the count silently comes out wrong. One queen per row is automatic because we always recurse to row + 1.

Trace n=4: row0 col1 → row1 col3 → row2 col0 → row3 col2 gives [1,3,0,2]; the mirror gives [2,0,3,1]. Two solutions.

Interactive Strategy Visualization

N-Queens (Recursive DFS)

Board: 4x4
N-Queens Goal: Place 4 queens so no two attack each other.
MINDSET

We place queens row-by-row. At each cell, we verify vertical and diagonal constraints. If a row has no valid spot, the entire branch is invalid.

PRUNING

A brute-force search of all queen positions would be N^(2N). Backtracking row-by-row with safety checks reduces this to O(N!) and even less in practice.

O(C(n², n) × n²) Choose Squares Then Validate
→
O(N!) Row-by-Row With Linear Safety Scan
→
O(N!) With Constant-Time Conflict Sets