• 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

Every earlier problem in this section enumerated answers that were all valid by construction — every subset is a subset, every permutation is a permutation. This one is different: most arrangements are illegal, and the interesting work is refusing to build them.

Stated plainly, the task is to choose n squares from n². For n = 8 that is C(64, 8) = 4,426,165,368 candidate boards, each then needing validation.

for squares in combinations(all_64_squares, 8):
    if no_two_attack(squares):
        record(squares)

Four billion candidates, and the overwhelming majority are absurd — most place several queens in the same row, which any human would reject at a glance.

Name the waste precisely: the search commits to all eight placements before checking any of them. A board with two queens in row 0 is doomed immediately, yet the enumeration continues to choose six more squares before discovering it. Every one of those later choices is wasted work on a branch that was already dead.

The fix has two halves, and both are worth extracting as general technique: make some illegal states unrepresentable, and detect the rest as early as possible.

No two queens may share a row, and there are n queens and n rows. So every row holds exactly one queen — not at most one, exactly one, since n queens must fit into n rows with no sharing.

That completely reframes the search. Do not choose squares. Choose, for each row, which column its queen occupies. A solution is now just a list of n column numbers.

The gain is dramatic. The search space drops from C(64,8) ≈ 4.4 billion to 8⁸ = 16.7 million, and — this is the real point — the row constraint can no longer be violated. It is not checked, because no representable arrangement breaks it.

Now notice a second constraint falls out the same way. No two queens may share a column either, so the list of column numbers has no repeats: it is a permutation of 0 to n-1. That cuts the space again, to 8! = 40,320.

Two of the three rules have been eliminated by choosing the right representation, before any checking code exists. Reducing four billion to forty thousand cost nothing but a change of viewpoint.

Only the diagonal rule remains, and it must be tested. The key decision is when.

Placing all n queens and then testing is still the leaf-checking mistake. Instead test at every placement: before putting a queen in a row, confirm it conflicts with nothing already placed. A conflict at row 3 kills the entire subtree beneath it — all the arrangements of rows 4 through 7 that would have followed. Pruning near the root of the tree saves exponentially more than pruning near the leaves.

So the question becomes how to test a diagonal quickly.

Two squares share a descending diagonal — down-right — when moving down one row moves right one column. So along such a diagonal, row and column increase together, which means row - col stays constant. Every descending diagonal has its own value of row - col.

Two squares share an ascending diagonal — down-left — when moving down one row moves left one column. There, row increases as column decreases, so row + col stays constant.

Check it concretely: squares (0,0), (1,1) and (2,2) all give row - col = 0, and they do lie on one descending diagonal. Squares (0,2), (1,1) and (2,0) all give row + col = 2, and they lie on one ascending diagonal.

So each square belongs to exactly one diagonal of each family, identified by those two numbers. Keeping a set of occupied values for each family makes a safety test three hash lookups — constant time, with no scanning of the board at all.

def solve_n_queens(n):
    result = []
    placement = []                        # placement[r] = column of the queen in row r
    cols, desc, asc = set(), set(), set() # occupied columns, row-col values, row+col values

    def build(row):
        if row == n:
            result.append(["." * c + "Q" + "." * (n - c - 1) for c in placement])
            return

        for col in range(n):
            if col in cols or (row - col) in desc or (row + col) in asc:
                continue                  # PRUNE: attacked, so skip without recursing

            cols.add(col)                 # CHOOSE
            desc.add(row - col)
            asc.add(row + col)
            placement.append(col)

            build(row + 1)                # EXPLORE

            placement.pop()               # UN-CHOOSE — all four pieces of state
            cols.remove(col)
            desc.remove(row - col)
            asc.remove(row + col)

    build(0)
    return result

Two solutions, and they are mirror images. The important moment is row 2 in the first branch: the whole subtree covering row 3 was eliminated by a single failed row, which is exactly the saving that leaf-checking would have forfeited.

Two ideas carry well beyond chessboards.

Choose a representation that makes illegal states unrepresentable. Switching from "pick n squares" to "pick a column per row" removed the row constraint entirely and reduced the search space by five orders of magnitude, with no checking code written. Before optimising a search, ask whether the encoding can absorb some of the constraints.

Prune as early as the constraint allows. Testing validity at the leaf wastes the entire subtree; testing at each step kills bad branches near the root. The general form is: check partial solutions for violations as soon as enough information exists to detect them.

The diagonal encoding is worth remembering on its own. Anti-diagonals share row + col; main diagonals share row - col. That identity appears in matrix diagonal traversals, diagonal sorting problems, and anywhere a grid must be grouped by diagonal.

Recognition signals: place k items subject to conflict rules, arrangement with mutual exclusions, colour the map, assign without collisions. This family is called constraint satisfaction, and Sudoku is the next one.

Train the reflex: when most arrangements are invalid, do not generate and filter. Encode what you can into the structure, and test the rest at the earliest moment it can fail.