Only boundary occupancy affects future placements. The past influences future only through cells crossing the current row boundary.

Sweep a curtain across the board. Everything behind it is complete; only dominoes poking through the curtain matter. Their boundary pattern is the profile.

What the function promises: Count tilings of a rows-by-cols board with 1×2 dominoes. Dimensions are nonnegative; rotate so the bitmask uses the smaller dimension.

def domino_tilings(rows, cols):
    if rows < 0 or cols < 0: raise ValueError("Negative dimension")
    if cols > rows: rows, cols = cols, rows
    dp = {0: 1}
    for _ in range(rows):
        next_dp = {}
        def fill(column, mask, next_mask, ways):
            while column < cols and mask & (1 << column): column += 1
            if column == cols:
                next_dp[next_mask] = next_dp.get(next_mask, 0) + ways
            else:
                if column+1 < cols and not mask & (1 << (column+1)):
                    fill(column+2, mask, next_mask, ways)
                fill(column+1, mask, next_mask | (1 << column), ways)
        for mask, ways in dp.items(): fill(0, mask, 0, ways)
        dp = next_dp
    return dp.get(0, 0)

assert domino_tilings(2,3) == 3
assert domino_tilings(3,3) == 0
assert domino_tilings(0,4) == 1

Work and storage: Roughly O(rows · cols · 2^cols) states/transitions for fixed small width; O(2^cols) stored profiles.

When to recognize it: The past influences future only through cells crossing the current row boundary.

Check before applying it: State count is exponential in width, so the method needs one small dimension.

OR each row’s obstacle mask into the incoming occupancy before generating placements.