precompute-relationships

name: precompute-relationships description: "For static relationships: graph structure, grid neighbors, constraint peers. Calculate once at module load, reference throughout program."

When to Use

Problem has fixed structure (grid, graph, hierarchy)
Same relationships queried repeatedly
Relationships can be computed from problem definition
Constraint problems with peers/neighbors
Any "what affects what" mapping

When NOT to Use

Relationships change during execution
Structure is too large to precompute
Only needed once

The Pattern

Compute all static relationships at module load time. Store in dicts for O(1) lookup.

# Define structure
rows = 'ABCDEFGHI'
cols = '123456789'

# Precompute all squares
squares = [r + c for r in rows for c in cols]

# Precompute all units (rows, cols, boxes)
unit_list = (
    [[r + c for c in cols] for r in rows] +  # Rows
    [[r + c for r in rows] for c in cols] +  # Columns
    [[r + c for r in rs for c in cs]         # Boxes
     for rs in ['ABC', 'DEF', 'GHI']
     for cs in ['123', '456', '789']]
)

# Precompute which units each square belongs to
units = {s: [u for u in unit_list if s in u] for s in squares}

# Precompute peers (squares that constrain this one)
peers = {s: set(sum(units[s], [])) - {s} for s in squares}

Example (from pytudes Sudoku.ipynb)

def cross(A, B):
    """Cross product of elements in A and B."""
    return [a + b for a in A for b in B]

digits = '123456789'
rows = 'ABCDEFGHI'
cols = digits

# All 81 squares
squares = cross(rows, cols)

# All 27 units
unitlist = ([cross(rows, c) for c in cols] +
            [cross(r, cols) for r in rows] +
            [cross(rs, cs)
             for rs in ('ABC', 'DEF', 'GHI')
             for cs in ('123', '456', '789')])

# units[s] = list of 3 units containing square s
units = {s: [u for u in unitlist if s in u]
         for s in squares}

# peers[s] = set of 20 squares that see square s
peers = {s: set(sum(units[s], [])) - {s}
         for s in squares}

# Now constraint propagation is fast:
def eliminate(values, s, d):
    for peer in peers[s]:  # O(1) lookup!
        eliminate(values, peer, d)

Key Principles

Compute once at load: Module-level, not function-level
Dict for O(1) lookup: units[square] not find_units(square)
Derive from structure: Units derive from grid definition
Transitive closure: Peers = union of all units minus self
Test the precomputation: Verify expected sizes and relationships