Broken Profile Dynamic Programming: Grid Tiling & Contour Line State Transitions

1. The Contour Line Paradigm: Jagged vs. Flat Boundaries

In classical grid DP, states represent entire horizontal rows. When advancing from row r to r + 1, an algorithm must evaluate all combinations of vertical dominoes extending downward and horizontal dominoes packed across columns.

In Broken Profile DP, the algorithm processes the grid cell by cell in standard raster order (row by row, left to right). The frontier dividing filled cells from unfilled cells is a contour line of length M + 1:

When focusing on a single cell (r, c), the decision is localized: we only inspect whether the cell above (r - 1, c) is empty, and whether the cell to the left (r, c - 1) is available for horizontal pairing.

2. Cell-by-Cell State Transitions

When advancing to cell (r, c) with profile mask:

1. Mandatory Vertical Fill: If the cell directly above (r - 1, c) is currently empty (the c-th bit of mask is 0), it can never be reached by future cells. It must be covered right now by placing a vertical domino on (r - 1, c) and (r, c). The new profile flips the c-th bit to 1.
2. Optional Decisions (when above cell is already filled):
   • Leave Empty: Do not place a domino on (r, c) yet. The c-th bit becomes 0 (waiting for a vertical domino from row r + 1).
   • Horizontal Fill: If c > 0 and the cell to the left (r, c - 1) is empty, place a horizontal domino covering (r, c - 1) and (r, c). Both corresponding bits become 1.

3. C++ Implementation: Domino Tiling in O(NM 2^M)

long long countTiling(int n, int m) {
    if ((n * m) % 2 != 0) return 0; // Odd area cannot be tiled with 1x2 dominos
    if (m > n) swap(n, m);          // Ensure m is the smaller dimension (m ≤ 12)

    int totalMasks = 1 << m;
    vector<long long> dp(totalMasks, 0);
    dp[totalMasks - 1] = 1; // Base case: all cells above row 0 are "filled"

    for (int r = 0; r < n; ++r) {
        for (int c = 0; c < m; ++c) {
            vector<long long> nextDp(totalMasks, 0);
            for (int mask = 0; mask < totalMasks; ++mask) {
                if (dp[mask] == 0) continue;

                if (mask & (1 << c)) {
                    // Above cell is filled: we can leave (r, c) empty
                    nextDp[mask ^ (1 << c)] += dp[mask];

                    // Or place horizontal domino if left cell is empty
                    if (c > 0 && !(mask & (1 << (c - 1)))) {
                        nextDp[mask | (1 << (c - 1))] += dp[mask];
                    }
                } else {
                    // Above cell is empty: MUST place vertical domino
                    nextDp[mask | (1 << c)] += dp[mask];
                }
            }
            dp = move(nextDp);
        }
    }

    return dp[totalMasks - 1];
}

4. Multi-State Plug Encodings: Trominoes & Polyomino Extensions

While 1 × 2 dominoes require only 1 bit per column (occupied or empty), more complex shapes such as L-trominoes or 1 × 3 straight bars demand multi-state profile representations:

• Base-3 (Trit) Encoding: For shapes requiring 3 possible boundary states (e.g., empty, covered once, covered twice), each column is assigned a trit t_c ∈ {0, 1, 2}. A profile of width M is packed into a base-3 integer mask ∈ [0, 3^M - 1].
• Trit Manipulation Arithmetic: Extracting the state of column c uses integer division and modulo: state = (mask / 3^c) % 3. Replacing column c with new state v subtracts the old component and adds v × 3^c.

5. Plug DP & Component Connectivity: Mondriaan's Dream Extension

When solving Hamiltonian paths, circuits, or maze connectivity on grids, tracking simple binary occupancy is insufficient because separate path segments might join into premature isolated loops.

Plug DP (Parenthesis Matching): Each contour plug represents an endpoint of an active path. Plugs are labeled using matching parentheses:

When two plugs meet at cell (r, c): if both are '(' and ')' of the same path, joining them closes the loop. This closure is permitted only at the very last cell of the entire board; at any earlier cell, closing the loop creates an invalid disconnected sub-cycle.

6. Matrix Exponentiation for Ultra-Long Grids (N → ∞)

When the grid width M is small (e.g., M ≤ 8) but grid length N is astronomical (e.g., N = 10^{18}), dynamic programming cell-by-cell in O(NM 2^M) is too slow.

Because the transitions across an entire row are strictly linear and time-invariant, we construct a 2^M × 2^M Row Transition Matrix T, where T[mask1][mask2] is the number of valid ways to transition from full row profile mask1 to mask2. The total number of valid tilings is computed via binary matrix exponentiation:

7. Engineering Invariants & Bitmask Dimension Swapping

• Mandatory Dimension Swapping: Because complexity scales exponentially with 2^M and linearly with N, the algorithm must verify m ≤ n upon entry. If m > n, swap dimensions: tiling an N × M grid is mathematically symmetric to tiling an M × N grid. Tiling a 100 × 10 grid takes milliseconds, whereas a 10 × 100 grid would overflow memory without swapping.
• Parity Feasibility Check: If the total grid area N × M is odd, covering the grid with 1 × 2 dominoes (each of area 2) is mathematically impossible. Return 0 immediately before allocating any vectors.

8. Algorithmic Comparison: Grid Profile DP Models