23. Count Non-Interfering Rack Placements

Problem

DeepMind's hardware team needs to place n accelerator jobs on an n x n rack grid, one job per row and one job per column, to avoid oversubscribing any single row's or column's power feed. As an additional constraint, no two jobs may also line up on a shared diagonal power rail.

Count the number of valid placements for a given n: exactly one job per row, one per column, and no two on the same diagonal.

Source: src/23_rack_interference_placement.py

def count_valid_placements(n: int) -> int:
    ...

Examples:
>>> count_valid_placements(4)
2

>>> count_valid_placements(1)
1

Step-by-Step Approach

1. Notice the "one per row, one per column" constraint means you can place jobs row by row and never need to check the row constraint explicitly — just choose one column per row.
2. Track three sets as you go: columns already used, and the two families of diagonals already used. A cell (row, col) sits on diagonal row - col (constant along one direction) and anti-diagonal row + col (constant along the other).
3. At each row, try every column. Skip any column already used, or whose diagonal/anti-diagonal is already occupied — placing there would interfere with an existing job.
4. If a column passes all three checks, place the job (add to all three sets), recurse into the next row, then remove it from all three sets before trying the next candidate column — classic backtracking: try, recurse, undo.
5. When row reaches n, every row has a valid job placed: increment the count of valid placements by one and return without recursing further.
6. The constant-time set lookups turn what looks like an n! search space into something that prunes itself heavily in practice, since most partial placements get rejected within the first few rows.

The key insight is encoding "no two jobs share a diagonal" as two simple integer invariants (row - col and row + col) rather than comparing every pair of placed jobs directly — that turns an O(n²) per-placement conflict check into three O(1) set lookups.

Reference solution

def count_valid_placements(n: int) -> int:
    if n == 0:
        return 1
    cols_used: set[int] = set()
    diag_used: set[int] = set()   # row - col is constant along a "\" diagonal
    anti_diag_used: set[int] = set()  # row + col is constant along a "/" diagonal
    count = 0

    def backtrack(row: int) -> None:
        nonlocal count
        if row == n:
            count += 1  # placed one job in every row without conflict: valid placement
            return
        for col in range(n):
            if col in cols_used or (row - col) in diag_used or (row + col) in anti_diag_used:
                continue  # placing here would interfere with an already-placed job
            cols_used.add(col)
            diag_used.add(row - col)
            anti_diag_used.add(row + col)
            backtrack(row + 1)
            # undo the choice before trying the next column in this row
            cols_used.remove(col)
            diag_used.remove(row - col)
            anti_diag_used.remove(row + col)

    backtrack(0)
    return count

Key Functions & Tricks

• row - col / row + col — the two integer invariants that identify a cell's two diagonals in O(1)
• Three parallel set() instances — turn "is this column/diagonal already used" into an O(1) membership check
• Add-recurse-remove — the core backtracking shape: commit to a choice, explore it fully, then undo it before trying the next
• Row-by-row placement — eliminates the row constraint entirely by construction instead of checking it explicitly
• nonlocal count — accumulates the total across all recursive branches without threading a return value back up

How to Recognize This Pattern