N-Queens — The Rival Queens

Boss 9: The Rival Queens

The finale, and the most storied problem in the dungeon: posed for chess boards in 1848, generalized to n, attacked by Gauss himself, and now the canonical demonstration of constraint-satisfaction backtracking, the technique behind Sudoku solvers, register allocation, and scheduling engines. Everything the dungeon taught assembles here, and one new trick joins: encoding diagonals as arithmetic.

The story

The chess society's display case, a 4×4 board, four queens. Queens attack along rows, columns, and both diagonals, unlimited range. The commission: arrangements where no queen threatens another, and they want the complete set.

First, shrink the search space by thinking before searching, the dungeon's oldest move. Four queens, four rows, and no two queens may share a row: every row holds exactly one queen. So an arrangement is just a choice of column for each row, [1, 3, 0, 2] means "row 0's queen in column 1, row 1's in column 3...", and rows are handled by construction, never checked again. 256 raw column-assignments (4⁴) instead of 1820 free placements. Constraints you build into the representation are constraints you never test.

Columns and diagonals remain, and here's the arithmetic trick that turns diagonal-checking from geometry into set-membership. Squares on the same ↘ diagonal share row - col (walk down-right: both grow, difference fixed). Squares on the same ↙ diagonal share row + col (down-left: row grows, col shrinks, sum fixed). Three hash sets, cols, diag, anti, and "is this square attacked?" becomes three O(1) lookups. No scanning the board, no loops over earlier queens.

The placement dance, row by row: try each column in the current row; if its three lookups all miss, place the queen (add to all three sets), descend to the next row, and on return, lift her (remove from all three), the un-choose now touching three pieces of state, the symmetry law at its heaviest load yet.

The problem, dressed up properly

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other. Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.

LeetCode 51. Output as painted boards, a list of strings per solution.

The naive attempt

Generate all ways to drop 4 queens on 16 squares, check each: C(16,4) = 1820 boards, each needing pairwise attack checks. Or, smarter already, all 4! = 24 permutations of columns (one per row, all distinct, that's Boss 3's machinery handling rows and columns) and check only diagonals. That second version is genuinely decent, and it still validates complete arrangements: a doomed first-two-queens pair spawns 2 full placements before dying at the check. The boss-grade version kills the pair the instant queen two touches a shared diagonal, no descendants, no autopsy. Same tree, guard moved to the moment of choice, Boss 7's placement law, at scale.

The weapon: one queen per row, three attack sets

def solve_n_queens(n: int) -> list[list[str]]:
    out = []
    queens = []                      # queens[r] = column of row r's queen
    cols, diag, anti = set(), set(), set()
 
    def place(row):
        if row == n:
            out.append(["".join("Q" if c == queens[r] else "."
                                for c in range(n)) for r in range(n)])
            return
        for col in range(n):
            if col in cols or (row - col) in diag or (row + col) in anti:
                continue                          # attacked: never placed
            queens.append(col)                    # choose, all four pieces
            cols.add(col)
            diag.add(row - col)
            anti.add(row + col)
            place(row + 1)                        # explore
            queens.pop()                          # un-choose, all four
            cols.discard(col)
            diag.discard(row - col)
            anti.discard(row + col)
    place(0)
    return out

Four mutations per choose, four reversals per un-choose, adjacent, symmetric, in matching order. This is the dungeon's symmetry law at maximum load, and the reason seasoned solvers group choose/un-choose lines visually: a missing discard here doesn't crash, it quietly convinces every later branch that a lifted queen still guards her diagonal, and solutions vanish without a trace.

Watching it work

n = 4, following row 0's first two attempts:

row 0, col 0: place. row 1: col 0 ✗(col) 1 ✗(diag) 2 ✓ place.
    row 2: 0 ✗ 1 ✗ 2 ✗ 3 ✗ → dead. lift row 1.
  row 1, col 3 ✓ place. row 2: only col 1 ✓ place.
    row 3: 0 ✗ 1 ✗ 2 ✗ 3 ✗ → dead. unwind all the way.
row 0, col 1: place. row 1: only col 3 ✓. row 2: only col 0 ✓.
    row 3: col 2 ✓ → SOLUTION:  . Q . .
                                 . . . Q
                                 Q . . .
                                 . . Q .
row 0, col 2: (mirror of above) → SOLUTION
row 0, cols 3: (mirror of col 0) → dead

2 solutions ✓

Watch the collapse: 256 column-assignments existed; the walk visited maybe two dozen partial states, because every attacked square was refused at the moment of placement and its entire subtree never existed. That disproportion, exponential possibility, slender actual walk, is backtracking's whole sales pitch, and N-Queens is its showroom. (For the record: n=8 has 92 solutions; n=9, 352. The count has no known closed formula, computers enumerate it, with exactly this algorithm.)

Gotchas

1. Checking only adjacent diagonals. Queens attack at any distance. Comparing a candidate against just the previous row's queen passes n=4 by luck and fails n=5. The row±col sets encode full-length diagonals by construction, trust arithmetic over geometry.

2. One of eight mutations missing. Four adds, four removes. The un-choose forgetting anti is invisible until a solution that needs that anti-diagonal goes missing. Smoke test: after place(0) returns, all three sets must be empty, Boss 1's empty-bag test, tripled.

3. Painting with shared row strings. Building the board once and mutating rows across solutions aliases the output lists (the path[:] bug wearing a chessboard). Paint fresh strings per solution, at the leaf.

4. row - col collisions with row + col. They live in separate sets for a reason: square (2,0) has difference 2 and sum 2, one merged set would let a ↘ diagonal veto an unrelated ↙ square. Two orientations, two sets, no shortcuts.

5. Symmetry "optimizations" that break enumeration. Mirroring half the solutions (try only cols < n/2 in row 0, reflect the rest) genuinely halves the work for counting, but emitting reflected boards correctly, including the odd middle column, is fiddly, and the problem wants every distinct board. Optimize the counting variant; enumerate the enumeration variant honestly.

Complexity

Time: O(n!)-ish, row r sees at most n-r unattacked columns, savagely pruned below that in practice. Painting costs O(n²) per solution. Space: O(n) for the sets, stack, and queen list.

Boss down. DUNGEON DOWN. XP gained. Crown earned.

Two arrangements go in the display case, mirror twins, as it happens, and the society's plaque credits "exhaustive analysis", which is exactly what it was: exhaustive in possibility, frugal in steps.

The full haul from Dungeon 9:

• The rhythm, forever: choose, explore, un-choose, symmetric to the last mutation, from one list to four structures
• Pruning at the moment of choice: guards before recursion, doomed universes never born, sorted breaks, tipping pans, mirror tests, attack sets
• Dedupe by construction: index floors for combinations, used-sets for permutations, twin-skips for duplicates, filters are confessions
• Representation kills constraints: one-queen-per-row, diagonals as row±col, the best check is the one made unnecessary
• Exponential outputs are the job; the craft is generating each answer exactly once and touching nothing else

Next dungeon: Heap / Priority Queue. From enumerating everything to caring only about the extremes: the k-th largest, the closest points, the busiest task. A tree that lives inside an array, never fully sorted, always instantly ready with its minimum, and the family of top-k problems that every stream, scheduler, and leaderboard runs on.

See you in Dungeon 10.