Broken-Profile DP: Counting Domino Tilings

1. Introduction & Motivation

A classic combinatorics-meets-algorithms question: in how many ways can you tile an $m \times n$ grid using dominoes (or trominoes, or other small tiles), so that every cell is covered exactly once and no tiles overlap or hang off the edge? The question sounds like it should have a closed-form answer, and for plain rectangles tiled with dominoes it does have an elegant one involving products of cosines — but that formula does not generalize once you add holes, forbidden cells, or other tile shapes. What generalizes is a dynamic programming technique.

The naive approach is to treat the whole grid as one flat state: has cell $(0,0)$ been filled, has $(0,1)$, and so on. That state has $2^{mn}$ possible values, which is only searchable for toy grids. The key realization is that you never need to know the fill status of the entire grid at once — only the status of a thin, moving boundary between the cells you have already decided and the cells you have not yet reached. If you process the grid cell by cell in row-major order and let $m$ be the smaller of the two grid dimensions, that boundary never needs more than $m$ bits to describe. The state space collapses from $2^{mn}$ down to $O(2^m)$, and the whole grid can be swept in $O(mn \cdot 2^m)$ time. This lesson builds that "profile" bitmask from first principles, derives the exact transition rules for domino tiling, and then shows how the same idea reframes as repeated matrix multiplication when the grid has an enormous number of rows.

2. Prerequisites

This lesson assumes you are already comfortable with representing a set as a bitmask and transitioning between masks in a DP table — the general mechanics of bitmask DP, including subset enumeration and submask iteration, are covered in Bitmask DP and Sum over Subsets and are not re-derived here. It also assumes the basic framing of dynamic programming over a 2D grid — processing cells in a fixed order and defining a DP state per cell — covered in Grid DP Fundamentals. Profile DP is best understood as grid DP where the "cell state" has been replaced by a boundary-of-cells state; if grid DP itself feels shaky, read that lesson first.

3. Core Insight: The Broken Profile

Picture sweeping a cursor left to right, top to bottom, one cell at a time. At the moment the cursor sits just before cell $(r, c)$, columns $0 \ldots c-1$ have already been decided in row $r$, while columns $c \ldots m-1$ have only been decided up through row $r-1$. The profile mask captures exactly this mixed frontier: for column $j \lt c$, bit $j$ says whether $(r, j)$ ended up filled by a tile that reaches into row $r+1$ (so it will show up as "already filled" when the cursor reaches $(r+1, j)$); for column $j \ge c$, bit $j$ says whether $(r-1, j)$ had a tile reaching down into $(r, j)$, i.e. whether $(r,j)$ is already filled before the cursor even gets there.

Both of these are really the same question asked at different times: is the cell currently at this column, at the frontier, filled? That uniform meaning is what makes a single $m$-bit mask sufficient, and it is why the profile is described as "broken" — a plain row-by-row profile DP would only ever ask this question at clean row boundaries, but here the question gets asked in the middle of a row too, every single cell.

4. A Concrete Example

5. Domino Tiling Count

Generalize the trace above into a full algorithm. Let rows and cols describe the grid, and always pass the smaller dimension as cols so the profile width stays small. Define dp[cell][mask] as the number of ways to have validly filled every cell before cell, in row-major order, such that mask is the current boundary profile. Only the previous layer of the DP is ever needed, so the implementation keeps a rolling dp array indexed only by mask.

For each cell at row row, column col (so col = cell % width and row = cell / width), and each mask with a nonzero count:

• Bit col of mask is set — this cell is already filled by a vertical domino placed one row above. There is no choice: clear bit col (that domino's coverage ends here, it will not extend further) and move to the next cell with the same count.
• Bit col of mask is clear — this cell is empty and must be covered now, by exactly one of:
  • A vertical domino, covering this cell and the one directly below it — only legal if a row below exists. This sets bit col in the resulting mask, since the cell below will find itself pre-filled when the cursor reaches it.
  • A horizontal domino, covering this cell and its right neighbor — only legal if a column to the right exists and that neighbor is not already pre-filled (bit col + 1 of mask must be clear). This sets bit col + 1, so when the cursor reaches that neighbor next, it falls into the "already filled" case above and is simply consumed.

After all rows × cols cells are processed, the answer is the count stored at mask = 0: every column must end with nothing dangling into a nonexistent next row. This has been verified against known small-grid tiling counts: a 2×2 grid gives 2, a 2×3 (or 3×2) grid gives 3, and a 4×4 grid gives 36.

def count_domino_tilings(rows, cols):
    """Count domino tilings of a rows x cols grid using broken-profile DP.

    `cols` becomes the profile width, so pass the smaller grid dimension
    as `cols` to keep 2**cols small.
    """
    width = cols
    height = rows
    num_masks = 1 << width
    dp = [0] * num_masks
    dp[0] = 1  # before any cell is decided, nothing is pre-filled

    for cell in range(height * width):
        col = cell % width
        row = cell // width
        next_dp = [0] * num_masks
        for mask in range(num_masks):
            ways = dp[mask]
            if ways == 0:
                continue
            if mask & (1 << col):
                # This cell is already filled by a vertical domino placed
                # one row above. No choice here: consume the bit and move on.
                next_dp[mask & ~(1 << col)] += ways
            else:
                # This cell is empty. Try each way to cover it.
                if row + 1 < height:
                    # Vertical domino: this cell and the one directly below it.
                    next_dp[mask | (1 << col)] += ways
                if col + 1 < width and not (mask & (1 << (col + 1))):
                    # Horizontal domino: this cell and its right neighbor.
                    next_dp[mask | (1 << (col + 1))] += ways
        dp = next_dp

    return dp[0]  # every column must end with no dangling vertical domino


print(count_domino_tilings(2, 2))  # 2
print(count_domino_tilings(2, 3))  # 3
print(count_domino_tilings(4, 4))  # 36

#include <iostream>
#include <vector>

long long countDominoTilings(int rows, int cols) {
    int width = cols;
    int height = rows;
    int numMasks = 1 << width;
    std::vector<long long> dp(numMasks, 0);
    dp[0] = 1;

    for (int cell = 0; cell < height * width; ++cell) {
        int col = cell % width;
        int row = cell / width;
        std::vector<long long> nextDp(numMasks, 0);
        for (int mask = 0; mask < numMasks; ++mask) {
            long long ways = dp[mask];
            if (ways == 0) continue;
            if (mask & (1 << col)) {
                nextDp[mask & ~(1 << col)] += ways;
            } else {
                if (row + 1 < height) {
                    nextDp[mask | (1 << col)] += ways;
                }
                if (col + 1 < width && !(mask & (1 << (col + 1)))) {
                    nextDp[mask | (1 << (col + 1))] += ways;
                }
            }
        }
        dp = nextDp;
    }
    return dp[0];
}

int main() {
    std::cout << "2x2: " << countDominoTilings(2, 2) << std::endl; // 2
    std::cout << "2x3: " << countDominoTilings(2, 3) << std::endl; // 3
    std::cout << "4x4: " << countDominoTilings(4, 4) << std::endl; // 36
}

public class DominoTiling {
    static long countDominoTilings(int rows, int cols) {
        int width = cols;
        int height = rows;
        int numMasks = 1 << width;
        long[] dp = new long[numMasks];
        dp[0] = 1;

        for (int cell = 0; cell < height * width; cell++) {
            int col = cell % width;
            int row = cell / width;
            long[] nextDp = new long[numMasks];
            for (int mask = 0; mask < numMasks; mask++) {
                long ways = dp[mask];
                if (ways == 0) continue;
                if ((mask & (1 << col)) != 0) {
                    nextDp[mask & ~(1 << col)] += ways;
                } else {
                    if (row + 1 < height) {
                        nextDp[mask | (1 << col)] += ways;
                    }
                    if (col + 1 < width && (mask & (1 << (col + 1))) == 0) {
                        nextDp[mask | (1 << (col + 1))] += ways;
                    }
                }
            }
            dp = nextDp;
        }
        return dp[0];
    }

    public static void main(String[] args) {
        System.out.println("2x2: " + countDominoTilings(2, 2)); // 2
        System.out.println("2x3: " + countDominoTilings(2, 3)); // 3
        System.out.println("4x4: " + countDominoTilings(4, 4)); // 36
    }
}

6. Row/Column Masks and the Transfer-Matrix View

The cell-by-cell sweep above is the most direct formulation, but it is not the only one. Instead of stepping cell by cell, picture stepping row by row. Between row $r$ and row $r+1$ there is a clean, unbroken profile: an $m$-bit mask saying, for each column, whether a vertical domino from row $r$ reaches into row $r+1$. Call this the entry mask for row $r+1$.

Given a fixed entry mask, there is some fixed number of ways to fill in the rest of row $r$'s cells — using horizontal dominoes and new vertical dominoes — that lead to each possible exit mask. Collect these counts into a $2^m \times 2^m$ transfer matrix $T$, where entry $(\text{mask}_1, \text{mask}_2)$ is the number of ways one row transitions from entry profile $\text{mask}_1$ to exit profile $\text{mask}_2$. The count of tilings of an $n$-row grid is then the $(0, 0)$ entry of $T^n$: start with nothing pre-filled, and after $n$ row-transitions end with nothing dangling.

Extracting Row Transitions from the Cell-by-Cell Logic

Building $T$ reuses exactly the same three transition rules from the previous section — only the driving loop changes. Instead of always starting from mask 0 and forbidding vertical placements in the last row, simulate one row's worth of cells ($m$ of them) starting from every possible entry mask, always allowing the vertical option, and record whatever exit masks are reachable. The "last row has no vertical option" rule from the cell-by-cell version is not needed here at all — it gets replaced by simply not multiplying by $T$ a further time once you run out of rows.

def build_transfer_matrix(width):
    """Build the 2**width x 2**width row-transfer matrix by reusing the
    exact same per-cell transition rules as the cell-by-cell DP, but
    starting from every possible entry mask and always allowing the
    vertical option (the "last row" cutoff is applied later, by how many
    times this matrix gets multiplied)."""
    size = 1 << width
    transfer = [[0] * size for _ in range(size)]

    for entry_mask in range(size):
        dp = {entry_mask: 1}
        for col in range(width):
            next_dp = {}
            for mask, ways in dp.items():
                if mask & (1 << col):
                    new_mask = mask & ~(1 << col)
                    next_dp[new_mask] = next_dp.get(new_mask, 0) + ways
                else:
                    # vertical: always allowed while building the matrix
                    new_mask = mask | (1 << col)
                    next_dp[new_mask] = next_dp.get(new_mask, 0) + ways
                    # horizontal
                    if col + 1 < width and not (mask & (1 << (col + 1))):
                        new_mask2 = mask | (1 << (col + 1))
                        next_dp[new_mask2] = next_dp.get(new_mask2, 0) + ways
            dp = next_dp
        for exit_mask, ways in dp.items():
            transfer[entry_mask][exit_mask] = ways

    return transfer

Once $T$ is built, matrix multiplication is associative, so $T^n$ can be computed by repeated squaring in $O(\log n)$ multiplications instead of $n$ of them. This is the entire payoff of the transfer-matrix reframing: it trades a linear dependence on the row count for a logarithmic one, at the cost of building and multiplying $2^m \times 2^m$ matrices instead of updating a $2^m$-length array. A full standalone program is not included here since the cell-by-cell implementation above is already complete and verified — this section shows how the same transitions repurpose into the matrix, which is the part worth internalizing.

7. Complexity Analysis

For the cell-by-cell sweep over an $m \times n$ grid (with $m$ chosen as the smaller dimension so $2^m$ stays manageable), every one of the $mn$ cells iterates over all $2^m$ masks doing $O(1)$ work per mask:

The transfer-matrix view changes the tradeoff entirely. Building the $2^m \times 2^m$ matrix costs roughly $O(2^m \times m)$, and each matrix multiplication costs $O(2^{3m})$ with schoolbook multiplication (or asymptotically less with fast matrix multiplication, though schoolbook is what is used in practice at these small sizes). Matrix exponentiation to the $n$-th power needs $O(\log n)$ multiplications:

8. Applications & Alternatives

The alternative to profile DP is usually either a closed-form combinatorial formula (available for plain rectangle domino tiling, but fragile — it breaks the moment you add holes or irregular shapes) or exhaustive backtracking (correct but exponential in the number of cells, not just the smaller dimension). Profile DP sits in between: it needs no special-case formula, and its cost depends only on $2^m$ rather than on the total cell count, which is exactly why choosing the smaller dimension as $m$ matters so much in practice.

9. Exercises

Easy

1. By hand-tracing or by running the code above, count the domino tilings of a 2×4 grid. Check your answer against the code.
2. Explain, in your own words, why the profile width should be the smaller of the two grid dimensions rather than the larger one.

Medium

1. Extend count_domino_tilings to also allow a single 1×1 "hole" — a cell that may be intentionally left empty rather than covered by a domino, at most once per tiling. (Hint: add a second dimension to the state tracking whether the hole has been used yet.)
2. Using your extension, count the number of such tilings-with-one-optional-hole for a 3×3 grid, and sanity-check the count for the special case where the hole is never used against the plain domino-tiling answer for a grid with one dimension odd.

Hard

1. Describe, without necessarily coding it, how the transition logic in Section 5 would need to change to count tilings using L-shaped or straight trominoes (3-cell tiles) instead of dominoes. Consider: how many cells ahead does a placed tile now reach, does the profile still need only $m$ bits or does it need more information per column, and how many orientations of each tromino must be tried at each empty cell. (Full code is optional; a precise design description is the goal.)

Review rhythm: tomorrow, re-derive the three transition cases (already-filled, vertical, horizontal) from a blank page without looking back. Next week, implement the DP from scratch in a language you did not use here. Several weeks later, build the transfer matrix for a small width by hand and confirm $T^n$ against the direct sweep. Finally, teach someone else why the profile is called "broken" and why matrix exponentiation only pays off when the row count, not the column count, is the extreme dimension.

10. Summary Cheat Sheet

• Direct 2D DP over a grid needs $2^{mn}$ states; broken-profile DP needs only $O(2^m)$ by tracking a thin boundary instead of the whole grid.
• The profile is a bitmask of width $m$ (the smaller grid dimension), one bit per column, meaning "is the frontier cell in this column currently filled."
• The profile is "broken" because the boundary cuts through the middle of a row during cell-by-cell processing, not cleanly between two full rows.
• Three transitions per cell: already filled (pass through, clear the bit), place a vertical domino (set the bit for this column), or place a horizontal domino (set the bit for the next column).
• Cell-by-cell sweep: $O(m \times n \times 2^m)$ time, $O(2^m)$ space.
• Row-by-row reframing turns the sweep into repeated multiplication by a $2^m \times 2^m$ transfer matrix, giving $O(2^{3m} \times \log n)$ via matrix exponentiation — a win only when $n$ is enormous and $m$ is small.
• The same boundary-bitmask idea generalizes to any grid-filling problem where legality depends only on a thin frontier, not the entire filled region.