precompute-relationships

precompute-relationships

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)