N-Queens

N-Queens is the classic example of backtracking with heavy pruning. The raw search space is huge, the real search is tiny, and the whole gap comes from checking each square the moment you consider it.

It also shows how much state one choice can carry: placing a queen changes four things, so undoing it takes four lines.

The problem

Place n queens on an n × n chessboard so that no two attack each other — no two share a row, a column or a diagonal. Return every such board, each as a list of strings where Q is a queen and . is empty.

• n = 4 → two boards: [".Q..", "...Q", "Q...", "..Q."] and ["..Q.", "Q...", "...Q", ".Q.."]. The first is the one in the diagram above.
• n = 1 → [["Q"]]. n = 2 and n = 3 → no boards at all.

Constraints: 1 ≤ n ≤ 9.

Clarifying questions

• Return boards, or only how many? Boards here; counting is a follow-up.
• Do mirror images count separately? Yes. The two boards for n = 4 are mirror images, and both are returned.
• Output format? A list of boards, each a list of n strings.

Approach 1: the simple way — try every column order, then check

Two queens in one row always attack, so there is exactly one queen per row. Two in one column also attack, so the columns used by rows 0 to n − 1 are a permutation of 0 to n − 1. Generate all n! permutations and keep those where no two queens share a diagonal.

1import itertools23def n_queens_brute(n: int) -> list[list[str]]:4    """Every column order, keeping those with no shared diagonal."""5    boards = []6    for cols in itertools.permutations(range(n)):7        down = {r - c for r, c in enumerate(cols)}8        up = {r + c for r, c in enumerate(cols)}9        if len(down) == n and len(up) == n:10            boards.append(["." * c + "Q" + "." * (n - c - 1) for c in cols])11    return boards

Why it is too slow. It is already smarter than trying all nⁿ boards (16.8 million for n = 8), but it still builds all 8! = 40,320 full orders for n = 8 and 362,880 for n = 9, each checked in O(n). Most of them fail at row 1 or 2: if queens in rows 0 and 1 already share a diagonal, all (n − 2)! completions below are built and rejected one by one.

The key insight

Check each square as you place it. Fill the board one row at a time. In each row, try each column, and reject a square at once if a queen above already covers its column or either diagonal. A clash in row 1 then kills the branch at row 1, not after the board is full.

For that to be fast, the "is this square attacked?" test must be O(1). The trick is that every diagonal has a number that is the same all along it:

• Down-right diagonals (top-left to bottom-right): row - col is the same on every square. (0,0), (1,1), (2,2) all give 0.
• Down-left diagonals (top-right to bottom-left): row + col is the same. (0,2), (1,1), (2,0) all give 2.

So keep three sets — used columns, used row - col values, used row + col values — and a square is safe exactly when its three numbers are in none of them.

Approach 2: backtracking with three sets

1def solve_n_queens(n: int) -> list[list[str]]:2    """Every placement of n non-attacking queens, one row at a time."""3    result: list[list[str]] = []4    queens: list[int] = []                 # queens[row] = column5    cols: set[int] = set()6    down: set[int] = set()                 # row - col: same along a down-right diagonal7    up: set[int] = set()                   # row + col: same along a down-left diagonal89    def backtrack(row: int) -> None:10        if row == n:11            result.append(["." * c + "Q" + "." * (n - c - 1) for c in queens])12            return13        for col in range(n):14            if col in cols or row - col in down or row + col in up:15                continue                   # attacked: prune the whole subtree16            queens.append(col); cols.add(col); down.add(row - col); up.add(row + col)17            backtrack(row + 1)18            queens.pop(); cols.remove(col); down.remove(row - col); up.remove(row + col)1920    backtrack(0)21    return result

The rows need no set: the recursion places exactly one queen per row by design. Four things change on each placement — queens and the three sets — so four things are undone.

Dry run for n = 4 until the first solution. queens lists the column in each filled row:

[1, 3, 0, 2] is the board .Q.., ...Q, Q..., ..Q.. Putting a queen in corner (0,0) led nowhere: every branch below it died by row 3.

Complexity. The first row has n choices, the second at most n − 1 (one column is taken), and so on, so the tree is bounded by O(n!) nodes, each doing O(1) work plus O(n²) to build a board when a solution is found. Pruning makes the real number far smaller: for n = 8 the search makes 2,057 calls to find all 92 solutions, against 40,320 orders for the brute force and 16,777,216 boards for the naive one. Working space is O(n) for the list, three sets and the stack.

Approach 3: count with bitmasks

When the question only wants the number of solutions (N-Queens II), replace the three sets with three integers whose bits mark attacked columns. Shifting the diagonal masks one bit per row moves each diagonal to the column it attacks in the next row.

1def total_n_queens(n: int) -> int:2    """Count solutions using three bitmasks instead of three sets."""3    full = (1 << n) - 145    def place(cols: int, down: int, up: int) -> int:6        if cols == full:7            return 1                            # every column holds a queen8        count = 09        free = full & ~(cols | down | up)       # squares in this row not attacked10        while free:11            bit = free & -free                  # lowest free square12            free -= bit13            count += place(cols | bit, ((down | bit) << 1) & full, (up | bit) >> 1)14        return count1516    return place(0, 0, 0)

Same tree, same O(n!) bound, but each step is a few bit operations and there is nothing to undo — the new masks are passed down as new values. It returns 92 for n = 8 and 724 for n = 10.

Edge cases

• n = 1 — one board, ["Q"].
• n = 2 and n = 3 — no solution; the code returns [] after the search finds only dead ends.
• Mirror images — both are returned. Do not try to remove symmetric boards unless asked.

Follow-ups

• Count only (N-Queens II) — the bitmask version above: no boards, no undo.
• Sudoku Solver — the same shape with three constraint sets (row, column, 3 × 3 box), and it helps to fill the most constrained cell first.
• Is a partly filled board still solvable? — put the given queens into the sets first, then run the same search from the first empty row.