4.18.9 — N-Queens

LeetCode 51 · Hard

The problem

Place n queens on an n × n board so that no two attack each other. A queen attacks along its row, its column, and both diagonals. Return every distinct arrangement.

n = 4  →  2 solutions

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

n is at most 9.

The pattern

Two reductions make this tractable, and the first one is free.

One queen per row. No two queens can share a row, and there are n queens and n rows, so every row holds exactly one. That means you never search over rows — you place row 0, then row 1, and so on, and the only decision is which column.

The search space drops from "choose 8 squares out of 64" (4 \times 10^9) to "choose a column for each row" (8^8 = 16.7 million). Before any pruning.

Then: prune at the moment of placing. Check the conflict as you choose a column, not after building a whole board. That takes 16.7 million down to about 2,000 positions actually explored.

This is the difference the constraint step makes, and it is why N-Queens is the reference problem for backtracking.

Naming the conflict groups

A candidate square (r, c) conflicts if another queen shares its column or either diagonal. Checking that by scanning the board is O(n) per candidate. You can make it O(1) by giving each group a name and keeping a set of the occupied ones.

Column: the name is c. Obvious.

The ↘ diagonal (top-left to bottom-right): moving down-right adds 1 to both r and c, so r − c stays constant along it.

The ↗ diagonal (top-right to bottom-left): moving down-left adds 1 to r and subtracts 1 from c, so r + c stays constant.

r − c on a 4×4 board          r + c on a 4×4 board

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

Every ↘ diagonal is one value of r − c; every ↗ diagonal is one value of r + c.

This is exactly the box-index idea from 4.4.8 Valid Sudoku — give each group a computable name, keep one set per group, and membership becomes O(1). Same technique, different geometry.

The solution

Python

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        result = []
        cols = set()
        diag = set()        # r − c   (the ↘ diagonals)
        anti = set()        # r + c   (the ↗ diagonals)
        placement = []      # placement[r] = the column used in row r

        def backtrack(r: int):
            if r == n:                                  # all rows filled
                result.append(['.' * c + 'Q' + '.' * (n - c - 1)
                               for c in placement])
                return

            for c in range(n):
                if c in cols or (r - c) in diag or (r + c) in anti:
                    continue                            # attacked — prune

                cols.add(c)
                diag.add(r - c)
                anti.add(r + c)
                placement.append(c)

                backtrack(r + 1)

                placement.pop()                         # undo all four
                anti.discard(r + c)
                diag.discard(r - c)
                cols.discard(c)

        backtrack(0)
        return result

TypeScript

function solveNQueens(n: number): string[][] {
  const result: string[][] = [];
  const cols = new Set<number>();
  const diag = new Set<number>();
  const anti = new Set<number>();
  const placement: number[] = [];

  function backtrack(r: number): void {
    if (r === n) {
      result.push(placement.map(c => '.'.repeat(c) + 'Q' + '.'.repeat(n - c - 1)));
      return;
    }
    for (let c = 0; c < n; c++) {
      if (cols.has(c) || diag.has(r - c) || anti.has(r + c)) continue;

      cols.add(c); diag.add(r - c); anti.add(r + c);
      placement.push(c);

      backtrack(r + 1);

      placement.pop();
      anti.delete(r + c); diag.delete(r - c); cols.delete(c);
    }
  }

  backtrack(0);
  return result;
}

Four pieces of state, four undos. Miss one and later branches see phantom queens. Writing the undos in reverse order of the additions is a habit that makes them easy to check by eye.

No board is stored during the search. placement[r] = c is all the information there is, and the board strings are built only when a solution is complete. That keeps the recursion light and the state trivial to undo.

The check is one line and O(1), which is the entire performance story.

Why r − c can be negative

r − c ranges from −(n−1) to n−1. A set handles negative keys with no trouble.

If you wanted arrays instead of sets — which is faster — offset the index by n − 1 so it lands in 0 … 2n−2:

diag = [False] * (2 * n - 1)     # index with (r - c + n - 1)
anti = [False] * (2 * n - 1)     # index with (r + c)

That offset is the only fiddly part, and it is worth mentioning as the optimisation you would make if the size mattered.

Complexity

O(n!) in the worst case: n choices in the first row, at most n−1 compatible in the second, and so on. In practice the diagonal constraints cut it far below n!.

O(n) space for the sets and the placement, plus the output.

There is no known polynomial algorithm for counting N-Queens solutions, and the counts are only known up to about n = 27, each one having taken serious computing effort. Saying that is a good way to answer "can you do better".

The bitmask version

For the fastest known implementation, replace the three sets with three integers, one bit per group.

def solveNQueens(self, n):
    result = []
    def backtrack(r, cols, diag, anti, placement):
        if r == n:
            result.append(...)
            return
        available = ~(cols | diag | anti) & ((1 << n) - 1)   # free columns
        while available:
            bit = available & -available                     # lowest set bit
            available -= bit
            c = bit.bit_length() - 1
            backtrack(r + 1, cols | bit, (diag | bit) << 1,
                      (anti | bit) >> 1, placement + [c])
    backtrack(0, 0, 0, 0, [])
    return result

The elegant part: shifting the diagonal masks by one as you move to the next row is exactly what a diagonal does geometrically. A ↘ diagonal moves one column right per row, hence << 1; a ↗ diagonal moves one left, hence >> 1. No arithmetic on indices at all.

available & -available isolates the lowest set bit, an idiom from 4.29.

Know it exists. Write the set version in an interview — it is readable and you can explain every line — and mention this if asked about speed.

Where this goes next

• N-Queens II — count the solutions instead of listing them. Same search, no board building.
• Sudoku Solver — this template with three group families (row, column, box) instead of three (column, two diagonals). The validity check from 4.4.8 becomes the pruning step, which is why the bitmask version of that check earns its keep.
• Constraint satisfaction generally — graph colouring, scheduling, timetabling. All of them are "assign values to variables subject to constraints", and all of them are this template with better heuristics on top (choose the most constrained variable first, and the least constraining value).

What the interviewer will push on

"How do you name the diagonals?" r − c and r + c. Derive it by saying what happens to each coordinate as you step along the diagonal.

"Why one queen per row?" They cannot share a row, and there are n of each, so it is forced. That reduction is the first thing to say.

"Where does the pruning happen and how much does it buy?" At the moment of placing, and it takes 8^8 = 16.7 million down to about 2,000.

"Can you make the check O(1)?" Sets or arrays keyed by the three group names — which it already is.

"How would you speed it up further?" Bitmasks, with the diagonal masks shifted per row.

One thing to volunteer: connect it to Valid Sudoku. "Both problems are 'this cell belongs to several overlapping groups' — I name each group with a formula and keep one set per group." That is the transferable idea, and it is why these two problems belong in the same head.

Next: 4.19 moves from trees to graphs, where a node can have many parents and cycles are allowed — and where the heap you built in 4.16 becomes the engine of shortest-path search.