On this page

Broken-Profile DP

How many ways are there to cover an 8×8 chessboard with 32 dominoes, each domino covering two neighbouring squares? The answer is 12,988,816. A backtracking search that places dominoes one by one would have to list all thirteen million tilings, and a 10×10 board has 258,584,046,368 of them — far too many to list. Yet a DP that sweeps the board one cell at a time and remembers only which cells on a thin boundary are already covered counts them in about steps.

That boundary is the profile, and because it has a step in it — part of it lies in the current row, part in the next — it is called a broken profile. This lesson builds the technique from the 2×n case (which turns out to be Fibonacci) to a general cell-by-cell DP, compares it with the simpler row-by-row version, applies it to placing non-attacking kings and choosing independent cells, and shows how, for a fixed width, the whole DP becomes one matrix that you can raise to the power .

This lesson assumes Bitmask DP (sets as integers) and Grid & Path DP (filling a grid in a safe order).

Why this exists

Grid DP works when each cell needs only a few numbers from its neighbours. Tiling and placement problems break that: whether a cell is free depends on which pieces stick into it from several earlier cells. A domino placed vertically in row 3 occupies a cell in row 4; a king in row 3 forbids three cells in row 4. The information that crosses from "done" to "not done" is not one number but a pattern along the boundary.

The key observation is that the pattern is the only thing that crosses. Everything above the boundary is finished and can never affect the future except through which boundary cells are already occupied. If the board is narrow — or so columns — the boundary has cells and possible patterns. So a DP with state "(position of the sweep, pattern on the boundary)" has states, polynomial in the board length .

The mathematics is old. Domino tilings are the dimer model of statistical physics; in 1961 P. W. Kasteleyn ("The statistics of dimers on a lattice", Physica 27) and independently H. N. V. Temperley and M. E. Fisher ("Dimer problem in statistical mechanics — an exact result", Philosophical Magazine 6) found a closed product formula for the number of domino tilings of an rectangle. The computational idea of sweeping a boundary and carrying a vector of pattern counts is the transfer-matrix method, introduced by Kramers and Wannier in 1941 for the Ising model. The cell-by-cell "broken" sweep is how competitive programmers and enumerative combinatorialists (for example Iwan Jensen's record enumerations of polyominoes) keep that vector small.

Pattern triggers

If the problem says or has…Think of…
"number of ways to tile / fill an board with dominoes (or L-pieces, or 1×2 / 2×1 bricks)", Broken-profile DP, mask = covered cells on the frontier
One side tiny (–), the other up to Profile over the short side, sweep along the long side
One side tiny, the other up to Transfer matrix + fast exponentiation
"no two chosen cells adjacent", "non-attacking kings", "students who can't cheat", "plant corn on fertile cells, no two adjacent"Row-mask DP or cell-by-cell profile over chosen cells
"paint an grid with colours, adjacent cells differ", Profile over colours (base- masks)
Only 2 or 3 rows (2×n, 3×n)Profile DP with tiny state, or a hand-derived linear recurrence
"count Hamiltonian cycles / paths in a grid", "single closed loop through all cells"Profile with connectivity information ("plug DP"; see Variations)
Both sides large, dominoes onlyKasteleyn's formula / Pfaffian (see Variations)
Pieces interact only with immediate neighboursCell-by-cell broken profile is the most general and simplest

The meta-trigger: a grid whose short side is suspiciously small, and pieces or constraints that cross from one row to the next. The state is "what the next row already knows".

Intuition & first principles

Warm-up: 2×n boards are Fibonacci

Take a board with 2 rows and columns. Look at the leftmost column. Either:

  • a vertical domino covers it — the rest is a 2×(n−1) board; or
  • a horizontal domino covers its top cell. Then the bottom cell can only be covered by another horizontal domino directly below. The two horizontal dominoes cover the first two columns; the rest is a 2×(n−2) board.

So , with (the empty board has one tiling: place nothing) and . That gives for : the Fibonacci numbers, .

flowchart LR
    B["2 x n board"] -->|"first column: one vertical domino"| C1["2 x (n-1) board"]
    B -->|"first two columns: two horizontal dominoes"| C2["2 x (n-2) board"]

Why the same argument gets messy for 3 rows

On a 3×n board, look at the first column. Three cells, and a domino can cover at most two of them vertically, so at least one horizontal domino sticks into column 2. Now column 2 is partly covered, and what remains is not a rectangle. You need to name the partly covered shapes: "column with the top cell already covered", "column with the bottom cell covered", and so on. Those names are the profiles. With 3 rows there are possible profiles; with rows, .

The profile, precisely

Sweep the board column by column, or — equivalently, and what the code does — row by row, from top to bottom. When you finish row , some dominoes from row stick down into row . Write a 1 for each cell of row that is already covered and a 0 for each free cell. That -bit string is the profile. Everything above row is irrelevant to the future.

Example with columns: after row is finished, vertical dominoes stick into columns 1 and 2 of row .

row r     : finished
row r+1   : . X X .        profile = 0110 (bit j = column j, column 0 on the right when written as a number)

The next row must cover the two free cells (columns 0 and 3) and may push new dominoes into row .

Two ways to step: row by row, or cell by cell

Row by row. From a profile cur for row , enumerate every way to finish row (cover its free cells with horizontal dominoes inside the row or with vertical dominoes that stick into row ). Each way produces a next profile nxt. dp[r+1][nxt] += dp[r][cur]. The transitions are generated by a small recursive search over the columns.

Cell by cell (the broken profile). Process one cell at a time in row-major order. The frontier is then a staircase: for the current cell , the profile describes cells — the part of the next row we have already pushed dominoes into — and cells — the rest of the current row. Still bits, but the boundary has a step at column : it is "broken".

processing cell (r, c) with m = 5, c = 2:

row r     :  done done [c]  ?    ?        bits 2, 3, 4 describe these cells of row r
row r+1   :   ?    ?    .   .    .        bits 0, 1 describe these cells of row r+1

At each cell there are only three cases (next section), so each step is per profile, and the whole DP is .

Mechanics

Cell-by-cell domino tiling: the three cases

State: dp[mask] = number of ways to have placed dominoes so that all cells before in row-major order are covered, and the frontier cells are covered exactly as mask says. Bit of mask refers to the frontier cell in column : in row if , in row if .

At cell , look at bit (the current cell):

  1. Bit = 1: already covered (by a vertical domino from above or a horizontal one from the left). Nothing to place. Moving on, the frontier cell for column becomes , which nothing covers yet: clear bit .
  2. Bit = 0, place a vertical domino covering and . Allowed if . The new frontier cell is covered: set bit .
  3. Bit = 0, place a horizontal domino covering and . Allowed if and bit is 0 (that cell is free). Set bit ; bit stays 0 because is still free.
flowchart TD
    Q{"bit c of mask?"} -->|"1: covered"| A["clear bit c, move on"]
    Q -->|"0: free"| V["vertical, if r+1 < n: set bit c"]
    Q -->|"0: free"| H["horizontal, if c+1 < m and bit c+1 = 0: set bit c+1"]

Start: before the first cell, nothing is covered: dp[0] = 1. Answer: after the last cell, the frontier is row (outside the board), which must be empty: dp[0].

Every domino is placed exactly once, at its top cell (vertical) or its left cell (horizontal). That is why the count has no duplicates (proof in Correctness).

Trace: a 3×2 board

rows, columns. Masks are written as two bits b1 b0 (column 1 on the left). The vector lists dp[00], dp[01], dp[10], dp[11] after processing each cell.

StepCellTransitions takendp after (00, 01, 10, 11)
0start—1, 0, 0, 0
1(0,0)from 00: vertical → 01; horizontal → 100, 1, 1, 0
2(0,1)from 01: bit 1 free, vertical → 11 (no room for horizontal); from 10: bit 1 covered → clear → 001, 0, 0, 1
3(1,0)from 00: vertical → 01, horizontal → 10; from 11: bit 0 covered → clear → 100, 1, 2, 0
4(1,1)from 01: vertical → 11; from 10 (2 ways): covered → clear → 002, 0, 0, 1
5(2,0)from 00 (2 ways): last row, no vertical; horizontal → 10; from 11: covered → clear → 100, 0, 3, 0
6(2,1)from 10 (3 ways): covered → clear → 003, 0, 0, 0

The answer is dp[00] = 3. The three tilings of a 3×2 board are: three horizontal dominoes; a vertical pair on top with one horizontal below; one horizontal on top with a vertical pair below. A 3×2 board is a 2×3 board turned sideways, and ✔.

Step 2 is where the profile "breaks": after cell (0,0), bit 0 already talks about row 1 while bit 1 still talks about row 0.

Row-by-row profile DP

The same problem, one whole row per step. For each cur profile, a recursive helper walks across the row and produces every nxt:

def row_transitions(m):
    """All (cur, nxt) pairs: filling one row whose pre-covered cells are `cur` pushes `nxt` into the next row."""
    pairs = []

    def fill(c, cur, nxt):
        if c == m:
            pairs.append((cur, nxt))
            return
        if (cur >> c) & 1:                           # already covered from above
            fill(c + 1, cur, nxt)
            return
        fill(c + 1, cur, nxt | (1 << c))             # vertical domino sticking down
        if c + 1 < m and not (cur >> (c + 1)) & 1:   # horizontal domino inside the row
            fill(c + 2, cur, nxt)

    for cur in range(1 << m):
        fill(0, cur, 0)
    return pairs


def tilings_row_by_row(n, m):
    pairs = row_transitions(m)
    dp = [0] * (1 << m)
    dp[0] = 1
    for _ in range(n):
        nd = [0] * (1 << m)
        for cur, nxt in pairs:
            nd[nxt] += dp[cur]
        dp = nd
    return dp[0]                                     # nothing may stick out of the last row


assert [tilings_row_by_row(2, k) for k in range(1, 8)] == [1, 2, 3, 5, 8, 13, 21]
assert tilings_row_by_row(8, 8) == 12988816
assert len(row_transitions(8)) == 985

Note the roles here: tilings_row_by_row(n, m) sweeps rows of width , so tilings_row_by_row(2, k) is a 2-row board of width .

How many transitions are there? Testing all pairs would be . Generating only the valid ones gives far fewer:

12345678910
valid transitions251229701694089852,3785,741
all pairs 416642561,0244,09616,38465,536262,1441,048,576

These are the Pell numbers: each is twice the previous plus the one before (), so they grow like . The reason: scanning a column, a cell is either pre-covered (1 way) or free with 2 choices, and a horizontal domino consumes two columns.

Row-by-row vs cell-by-cell

ApproachWork per rowNeeds
Row by row, test all pairs (plus a validity check)65,5361,048,576a fast "is this pair valid?" test
Row by row, generated transitionsnumber of valid transitions9855,741a recursive generator per piece type
Cell by cell (broken profile) states × at most 2 moves2,048 states10,240 statesthree local cases

For plain dominoes, generated row transitions are actually competitive with cell by cell. The cell-by-cell version wins on generality and simplicity: the transition is three local cases no matter how strange the piece set or constraint, there is no generator to write or debug, and the cost is predictably even when the number of row transitions explodes (with L-trominoes, extra colours, or obstacles, the row-transition count can approach ). It also handles blocked cells trivially: a blocked cell behaves like "bit already set".

Placing non-attacking kings (row masks)

A king attacks the 8 surrounding cells. Count the ways to place kings on an board so that no two attack each other.

Row by row is the natural fit, because the constraint is between a row and the next:

  • A row mask is valid by itself if no two kings in the row are adjacent: s & (s << 1) == 0. The number of such masks of length is the Fibonacci number (55 for ).
  • Two consecutive rows (above) and (below) are compatible if no king in is directly below or diagonally below a king in : s & t == 0, s & (t << 1) == 0, s & (t >> 1) == 0.
def count_king_placements(n, m):
    good = [s for s in range(1 << m) if not s & (s << 1)]
    dp = {s: 1 for s in good}                       # first row
    for _ in range(n - 1):
        nd = {t: 0 for t in good}
        for s, ways in dp.items():
            for t in good:
                if not (s & t or s & (t << 1) or s & (t >> 1)):
                    nd[t] += ways
        dp = nd
    return sum(dp.values())


assert count_king_placements(3, 3) == 35
assert count_king_placements(8, 8) == 1355115601

Adding "exactly kings" (the classic Little Kings problem) adds a count dimension: dp[row][mask][kings so far]. On a 3×3 board there are 16 ways to place exactly 2 kings, on a 4×4 board 79 ways to place exactly 4.

Maximum-weight independent set in a grid graph (cell by cell)

Each cell has a weight; choose cells with maximum total weight so that no two chosen cells share an edge (orthogonal neighbours). This is the maximum-weight independent set problem on a grid graph — NP-hard on general graphs, but a narrow grid has small pathwidth (the frontier is a separator of size ), and profile DP is exactly a DP over that path decomposition.

Cell by cell: bit of the mask says whether the latest processed cell in column is chosen. At , the cell above is bit (still the row value) and the cell to the left is bit (already the row value).

def max_independent_grid(w):
    n, m = len(w), len(w[0])
    NEG = float("-inf")
    dp = [NEG] * (1 << m)
    dp[0] = 0
    for r in range(n):
        for c in range(m):
            nd = [NEG] * (1 << m)
            for mask, val in enumerate(dp):
                if val == NEG:
                    continue
                skip = mask & ~(1 << c)                       # do not choose (r, c)
                nd[skip] = max(nd[skip], val)
                up = (mask >> c) & 1
                left = c > 0 and (mask >> (c - 1)) & 1
                if not up and not left:                        # choose (r, c)
                    take = mask | (1 << c)
                    nd[take] = max(nd[take], val + w[r][c])
            dp = nd
    return max(dp)


assert max_independent_grid([[1, 2, 3], [4, 5, 6], [7, 8, 9]]) == 25     # 1 + 3 + 5 + 7 + 9
assert max_independent_grid([[5, 1], [1, 5]]) == 10

The same DP with chosen cells forbidden on diagonals is LeetCode 1349 (Maximum Students Taking Exam); with "count" instead of "max" it counts independent sets.

Trominoes and other pieces

An L-shaped tromino covers three cells of a 2×2 square. On a 2×n board with dominoes and L-trominoes (LeetCode 790), a short case analysis gives with : . On wider boards, an L-tromino placed at cell can touch — a cell behind the staircase — so the plain broken profile is not enough. Two standard fixes: carry a profile of bits (the staircase plus the one cell diagonally behind it), or process each 2×2 window's placements at their top-left cell so that every piece fits the "current cell + right + below" pattern. Both keep the shape with a slightly larger constant.

def domino_tromino_2xn(n, mod=10**9 + 7):
    t = [1, 1, 2]
    for i in range(3, n + 1):
        t.append((2 * t[i - 1] + t[i - 3]) % mod)
    return t[n]


assert [domino_tromino_2xn(k) for k in range(1, 7)] == [1, 2, 5, 11, 24, 53]

Huge n: transfer matrices and matrix exponentiation

Fix the width . One full row of the row-by-row DP is a linear map on the vector of profile counts:

So , and the number of tilings of an board is . is the transfer matrix. With fast exponentiation by repeated squaring, needs matrix multiplications of size : time. For that is a 8×8 matrix, and takes 60 squarings. Matrix Exponentiation covers the exponentiation in depth.

def transfer_matrix(m):
    T = [[0] * (1 << m) for _ in range(1 << m)]

    def fill(c, cur, nxt):
        if c == m:
            T[nxt][cur] += 1
            return
        if (cur >> c) & 1:
            fill(c + 1, cur, nxt)
            return
        fill(c + 1, cur, nxt | (1 << c))
        if c + 1 < m and not (cur >> (c + 1)) & 1:
            fill(c + 2, cur, nxt)

    for cur in range(1 << m):
        fill(0, cur, 0)
    return T


def mat_mul(A, B, mod):
    k = len(A)
    C = [[0] * k for _ in range(k)]
    for i in range(k):
        for t in range(k):
            if A[i][t]:
                a, row_b, row_c = A[i][t], B[t], C[i]
                for j in range(k):
                    row_c[j] = (row_c[j] + a * row_b[j]) % mod
    return C


def tilings_huge(n, m, mod=10**9 + 7):
    T = transfer_matrix(m)
    k = len(T)
    R = [[int(i == j) for j in range(k)] for i in range(k)]   # identity
    while n:
        if n & 1:
            R = mat_mul(R, T, mod)
        T = mat_mul(T, T, mod)
        n >>= 1
    return R[0][0]


assert [tilings_huge(k, 3) for k in range(1, 9)] == [0, 3, 0, 11, 0, 41, 0, 153]
assert tilings_huge(8, 8) == 12988816

For 3×n the sequence (even ) satisfies (, ); the Cayley–Hamilton theorem guarantees that some such linear recurrence of order at most always exists, and the Berlekamp–Massey algorithm can find it from the first few terms.

The ladder: brute force → better → optimal

Problem: count domino tilings of an board, , small.

Rung 1: backtracking

Find the first empty cell in row-major order; try a horizontal domino, then a vertical one; recurse. Every tiling is generated once (the first empty cell must be covered by a domino whose top-left is that cell).

def tilings_brute(n, m):
    covered = [[False] * m for _ in range(n)]

    def go(i):
        while i < n * m and covered[i // m][i % m]:
            i += 1
        if i == n * m:
            return 1
        r, c = divmod(i, m)
        total = 0
        if c + 1 < m and not covered[r][c + 1]:
            covered[r][c] = covered[r][c + 1] = True
            total += go(i + 1)
            covered[r][c] = covered[r][c + 1] = False
        if r + 1 < n:
            covered[r][c] = covered[r + 1][c] = True
            total += go(i + 1)
            covered[r][c] = covered[r + 1][c] = False
        return total

    return go(0)


assert tilings_brute(4, 4) == 36
assert tilings_brute(6, 6) == 6728

Time is at least proportional to the number of tilings, which grows exponentially in the area: about asymptotically (the per-cell growth constant is , where is Catalan's constant). The 8×8 board takes seconds in Python; 10×10 is hopeless. Its value: an oracle for the DP on small boards.

Rung 2: memoised backtracking = profile DP

Notice that the recursion above, at the moment it reaches cell , depends only on and on which of the next cells are already covered (nothing beyond that can be covered yet, since dominoes reach at most one row down). Memoise on and you have the broken-profile DP: states, work each.

Rung 3: row-by-row with all pairs

if every pair is tested. Simple, but per row.

Rung 4: cell by cell (or generated row transitions)

time, memory with two rolling arrays. For , : steps.

Rung 5: transfer matrix power

For up to : . Only for small ( or so); beyond that, find the linear recurrence with Berlekamp–Massey and use Kitamasa/polynomial methods.

Side rung: Kasteleyn's formula (dominoes only)

multiplications for any board size. For the 8×8 board it gives 12,988,816 (in floating point it comes out as 12988816.00000004; round it). Exact large values need a Pfaffian (a determinant computation) over integers or modulo a prime. It is specific to dominoes on planar graphs; profile DP handles any local rule.

RungMethodTimeSpaceWhy it is better
1Backtracking, exponential in Baseline; obviously correct
2Memoised backtrackingSame sub-question (cell, frontier) answered once
3Row by row, all pairsNo recursion, rolling arrays
4Cell by cell times faster than rung 3; three-case transitions
5Transfer matrix powerHandles
sideKasteleyn productAny size, but dominoes only and floating point

Correctness

Bijection between tilings and decision sequences. Process cells in row-major order. In any tiling, every domino has a unique first cell in that order: its left cell (horizontal) or its top cell (vertical). Define the decision at cell as: "covered already" if is not the first cell of its domino, otherwise "vertical" or "horizontal". This maps each tiling to exactly one sequence of decisions, and two different tilings give different sequences (the sequence lists every domino). Conversely, a sequence the DP accepts (never covers a cell twice, never leaves a cell uncovered, never sticks out of the board) describes a tiling. So counting accepted sequences counts tilings.

The mask captures exactly what the future needs. Invariant: when the DP is about to process , bit of the mask equals "the frontier cell of column is covered", where the frontier cell is for and for . Any cell after in row-major order that is not on the frontier is uncovered, because a domino placed at an earlier cell reaches at most one cell to the right or one cell down, and both of those are frontier cells. So two partial placements with the same mask have exactly the same set of valid completions. That justifies merging them into one count.

The three cases preserve the invariant. Moving from to the next cell replaces frontier cell by in column :

  • Covered already: is not covered by anything yet (only a vertical domino placed at could cover it), so bit becomes 0 ✔.
  • Vertical: covers and ; bit becomes 1 ✔. It needs .
  • Horizontal: covers and ; the latter is frontier column , which must have been 0 and becomes 1; is uncovered, bit is 0 ✔.

At the end of a row the staircase straightens: all bits describe row , matching the row-by-row profile. After the last cell all bits describe row , which does not exist, so only mask 0 is a valid tiling. ∎

Transfer matrix. One row of the DP is the linear map . Composition of rows is matrix multiplication, and matrix multiplication is associative, so can be computed by repeated squaring in any grouping — that is all fast exponentiation needs.

Complexity

ProblemTimeMemory
Domino tilings, cell by cell (two rolling arrays)
Domino tilings, row by row with generated transitions, valid transitions
Domino tilings, row by row testing all pairs
Non-attacking kings, row masks,
Max independent set, cell by cell
Transfer matrix power

Always put the shorter side in the mask: a 1000×10 board costs steps; the same board with the mask over the 1000 side is impossible.

Count sizes: 8×8 = 12,988,816 fits in 32 bits; 10×10 = 258,584,046,368 needs 64 bits; 12×12 = 53,060,477,521,960,000 is about and still fits in signed 64-bit, but 14×14 does not. Problems with larger boards always give a modulus.

Implementation

Domino tiling count via the cell-by-cell broken profile, in four languages. Each program checks the 2×n Fibonacci values, the 3×n values, 4×4 = 36, 6×6 = 6,728, 8×8 = 12,988,816 and 10×10 = 258,584,046,368, and compares with backtracking on every board up to 6×6.

def count_domino_tilings(n: int, m: int) -> int:
    """Number of domino tilings of an n x m board (cell-by-cell broken profile)."""
    if m > n:
        n, m = m, n                          # keep the mask over the shorter side
    if (n * m) % 2:
        return 0
    dp = [0] * (1 << m)
    dp[0] = 1
    for r in range(n):
        for c in range(m):
            nd = [0] * (1 << m)
            bit = 1 << c
            for mask, ways in enumerate(dp):
                if not ways:
                    continue
                if mask & bit:                               # covered from above or the left
                    nd[mask ^ bit] += ways
                    continue
                if r + 1 < n:                                # vertical: (r,c) + (r+1,c)
                    nd[mask | bit] += ways
                if c + 1 < m and not mask & (bit << 1):      # horizontal: (r,c) + (r,c+1)
                    nd[mask | (bit << 1)] += ways
            dp = nd
    return dp[0]


def tilings_brute(n: int, m: int) -> int:
    covered = [[False] * m for _ in range(n)]

    def go(i: int) -> int:
        while i < n * m and covered[i // m][i % m]:
            i += 1
        if i == n * m:
            return 1
        r, c = divmod(i, m)
        total = 0
        if c + 1 < m and not covered[r][c + 1]:
            covered[r][c] = covered[r][c + 1] = True
            total += go(i + 1)
            covered[r][c] = covered[r][c + 1] = False
        if r + 1 < n:
            covered[r][c] = covered[r + 1][c] = True
            total += go(i + 1)
            covered[r][c] = covered[r + 1][c] = False
        return total

    return go(0)


def main() -> None:
    fib = [1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
    assert [count_domino_tilings(2, k) for k in range(1, 11)] == fib
    assert [count_domino_tilings(3, k) for k in range(1, 9)] == [0, 3, 0, 11, 0, 41, 0, 153]
    assert count_domino_tilings(4, 4) == 36
    assert count_domino_tilings(6, 6) == 6728
    assert count_domino_tilings(8, 8) == 12988816
    assert count_domino_tilings(10, 10) == 258584046368
    for a in range(1, 7):
        for b in range(1, 7):
            assert count_domino_tilings(a, b) == tilings_brute(a, b), (a, b)
    print("8x8:", count_domino_tilings(8, 8))


if __name__ == "__main__":
    main()
public class DominoTiling {
    static long countDominoTilings(int n, int m) {
        if (m > n) { int t = n; n = m; m = t; }       // mask over the shorter side
        if ((n * m) % 2 != 0) return 0;
        long[] dp = new long[1 << m];
        dp[0] = 1;
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < m; c++) {
                long[] nd = new long[1 << m];
                int bit = 1 << c;
                for (int mask = 0; mask < (1 << m); mask++) {
                    long ways = dp[mask];
                    if (ways == 0) continue;
                    if ((mask & bit) != 0) { nd[mask ^ bit] += ways; continue; }
                    if (r + 1 < n) nd[mask | bit] += ways;                                  // vertical
                    if (c + 1 < m && (mask & (bit << 1)) == 0) nd[mask | (bit << 1)] += ways; // horizontal
                }
                dp = nd;
            }
        }
        return dp[0];
    }

    static boolean[][] covered;

    static long brute(int n, int m, int i) {
        while (i < n * m && covered[i / m][i % m]) i++;
        if (i == n * m) return 1;
        int r = i / m, c = i % m;
        long total = 0;
        if (c + 1 < m && !covered[r][c + 1]) {
            covered[r][c] = covered[r][c + 1] = true;
            total += brute(n, m, i + 1);
            covered[r][c] = covered[r][c + 1] = false;
        }
        if (r + 1 < n) {
            covered[r][c] = covered[r + 1][c] = true;
            total += brute(n, m, i + 1);
            covered[r][c] = covered[r + 1][c] = false;
        }
        return total;
    }

    static void check(boolean ok, String msg) { if (!ok) throw new AssertionError(msg); }

    public static void main(String[] args) {
        long[] fib = {1, 2, 3, 5, 8, 13, 21, 34, 55, 89};
        for (int k = 1; k <= 10; k++) check(countDominoTilings(2, k) == fib[k - 1], "2xn");
        long[] three = {0, 3, 0, 11, 0, 41, 0, 153};
        for (int k = 1; k <= 8; k++) check(countDominoTilings(3, k) == three[k - 1], "3xn");
        check(countDominoTilings(4, 4) == 36, "4x4");
        check(countDominoTilings(6, 6) == 6728, "6x6");
        check(countDominoTilings(8, 8) == 12988816L, "8x8");
        check(countDominoTilings(10, 10) == 258584046368L, "10x10");
        for (int a = 1; a <= 6; a++)
            for (int b = 1; b <= 6; b++) {
                covered = new boolean[a][b];
                check(countDominoTilings(a, b) == brute(a, b, 0), "brute " + a + "x" + b);
            }
        System.out.println("8x8: " + countDominoTilings(8, 8));
    }
}
#include <cassert>
#include <cstdint>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

int64_t countDominoTilings(int n, int m) {
    if (m > n) swap(n, m);                       // mask over the shorter side
    if ((n * m) % 2) return 0;
    vector<int64_t> dp(1 << m, 0), nd(1 << m);
    dp[0] = 1;
    for (int r = 0; r < n; ++r) {
        for (int c = 0; c < m; ++c) {
            fill(nd.begin(), nd.end(), 0);
            int bit = 1 << c;
            for (int mask = 0; mask < (1 << m); ++mask) {
                int64_t ways = dp[mask];
                if (!ways) continue;
                if (mask & bit) { nd[mask ^ bit] += ways; continue; }
                if (r + 1 < n) nd[mask | bit] += ways;                              // vertical
                if (c + 1 < m && !(mask & (bit << 1))) nd[mask | (bit << 1)] += ways; // horizontal
            }
            swap(dp, nd);
        }
    }
    return dp[0];
}

int64_t brute(vector<vector<bool>>& cov, int n, int m, int i) {
    while (i < n * m && cov[i / m][i % m]) ++i;
    if (i == n * m) return 1;
    int r = i / m, c = i % m;
    int64_t total = 0;
    if (c + 1 < m && !cov[r][c + 1]) {
        cov[r][c] = cov[r][c + 1] = true;
        total += brute(cov, n, m, i + 1);
        cov[r][c] = cov[r][c + 1] = false;
    }
    if (r + 1 < n) {
        cov[r][c] = cov[r + 1][c] = true;
        total += brute(cov, n, m, i + 1);
        cov[r][c] = cov[r + 1][c] = false;
    }
    return total;
}

int main() {
    int64_t fib[] = {1, 2, 3, 5, 8, 13, 21, 34, 55, 89};
    for (int k = 1; k <= 10; ++k) assert(countDominoTilings(2, k) == fib[k - 1]);
    int64_t three[] = {0, 3, 0, 11, 0, 41, 0, 153};
    for (int k = 1; k <= 8; ++k) assert(countDominoTilings(3, k) == three[k - 1]);
    assert(countDominoTilings(4, 4) == 36);
    assert(countDominoTilings(6, 6) == 6728);
    assert(countDominoTilings(8, 8) == 12988816);
    assert(countDominoTilings(10, 10) == 258584046368LL);
    for (int a = 1; a <= 6; ++a)
        for (int b = 1; b <= 6; ++b) {
            vector<vector<bool>> cov(a, vector<bool>(b, false));
            assert(countDominoTilings(a, b) == brute(cov, a, b, 0));
        }
    cout << "8x8: " << countDominoTilings(8, 8) << "\n";
}
function countDominoTilings(n: number, m: number): number {
  if (m > n) [n, m] = [m, n];                      // mask over the shorter side
  if ((n * m) % 2) return 0;
  let dp = new Array<number>(1 << m).fill(0);
  dp[0] = 1;
  for (let r = 0; r < n; r++) {
    for (let c = 0; c < m; c++) {
      const nd = new Array<number>(1 << m).fill(0);
      const bit = 1 << c;
      for (let mask = 0; mask < (1 << m); mask++) {
        const ways = dp[mask];
        if (!ways) continue;
        if (mask & bit) { nd[mask ^ bit] += ways; continue; }
        if (r + 1 < n) nd[mask | bit] += ways;                                    // vertical
        if (c + 1 < m && !(mask & (bit << 1))) nd[mask | (bit << 1)] += ways;     // horizontal
      }
      dp = nd;
    }
  }
  return dp[0];                                    // exact while counts stay below 2^53
}

function tilingsBrute(n: number, m: number): number {
  const cov: boolean[][] = Array.from({ length: n }, () => new Array<boolean>(m).fill(false));
  const go = (start: number): number => {
    let i = start;
    while (i < n * m && cov[Math.floor(i / m)][i % m]) i++;
    if (i === n * m) return 1;
    const r = Math.floor(i / m), c = i % m;
    let total = 0;
    if (c + 1 < m && !cov[r][c + 1]) {
      cov[r][c] = cov[r][c + 1] = true;
      total += go(i + 1);
      cov[r][c] = cov[r][c + 1] = false;
    }
    if (r + 1 < n) {
      cov[r][c] = cov[r + 1][c] = true;
      total += go(i + 1);
      cov[r][c] = cov[r + 1][c] = false;
    }
    return total;
  };
  return go(0);
}

function assert(ok: boolean, msg: string): void {
  if (!ok) throw new Error(msg);
}

const fib = [1, 2, 3, 5, 8, 13, 21, 34, 55, 89];
for (let k = 1; k <= 10; k++) assert(countDominoTilings(2, k) === fib[k - 1], "2xn");
const three = [0, 3, 0, 11, 0, 41, 0, 153];
for (let k = 1; k <= 8; k++) assert(countDominoTilings(3, k) === three[k - 1], "3xn");
assert(countDominoTilings(4, 4) === 36, "4x4");
assert(countDominoTilings(6, 6) === 6728, "6x6");
assert(countDominoTilings(8, 8) === 12988816, "8x8");
assert(countDominoTilings(10, 10) === 258584046368, "10x10");
for (let a = 1; a <= 6; a++)
  for (let b = 1; b <= 6; b++) assert(countDominoTilings(a, b) === tilingsBrute(a, b), `brute ${a}x${b}`);
console.log("8x8:", countDominoTilings(8, 8));

Notes: the bit for column is 1 << c, and "the cell to the right in the current row" is bit << 1. The odd-area early return is an optimisation only; the DP returns 0 for odd areas on its own. Counts exceed 64 bits from about 14×14, and JavaScript numbers lose exactness above (12×12 already exceeds it); for those, use a modulus or BigInt.

Real-world uses

  • Statistical physics: the dimer model. Domino tilings are dimer coverings of the square lattice; their count gives the entropy of a system of diatomic molecules adsorbed on a surface. Kasteleyn (1961) and Temperley–Fisher (1961) solved the square lattice exactly; for lattices without a closed form, physicists use transfer matrices on strips of width and extrapolate in .
  • Enumerative combinatorics records. Transfer-matrix algorithms with a broken (cell-by-cell) frontier hold the records for counting polyominoes and self-avoiding polygons on the square lattice (Iwan Jensen, "Enumerations of lattice animals and trees", Journal of Statistical Physics 102, 2001, and later papers). They run the same "sweep a frontier, carry a table of frontier states" loop as this lesson, with connectivity information in the state.
  • Exact inference in grid-structured graphical models. In image processing and spatial statistics, a Markov random field on an pixel grid can be solved exactly by sweeping a row (or a staircase) of pixels as the separator — the junction-tree algorithm on a path decomposition. The cost is per step for labels per pixel, which is exactly why exact inference is used only for narrow strips and approximate methods (belief propagation, graph cuts) for full images (Koller and Friedman, Probabilistic Graphical Models, 2009, chapters 9–10 on variable elimination and clique trees).
  • Pathwidth/treewidth algorithms. Many NP-hard graph problems are solved in time exponential only in the width of a path or tree decomposition; on a grid of width the natural path decomposition has width about , and the DP over it is broken-profile DP (Cygan et al., Parameterized Algorithms, Springer 2015, chapter 7).
  • Puzzle and game tooling. Counting or enumerating completions of tiling puzzles, and generating random tilings uniformly (sample backwards through the DP table, choosing each transition with probability proportional to its count).

Pitfalls and edge cases

  • Mask over the long side. Always swap so that . A 3×1000 board has 8 profiles; a 1000×3 board treated with cannot run.
  • Forgetting that a covered cell clears its bit. In case 1 you must clear bit ; leaving it set claims is covered and silently undercounts.
  • Horizontal into a covered cell. Check bit before placing a horizontal domino; it may already be covered by a vertical domino from the row above.
  • Vertical out of the board. In the last row, only horizontal dominoes or "covered" are allowed. Equivalently, take dp[0] at the end — but the explicit check avoids spending time on doomed states.
  • Reading the answer from the wrong mask. The answer is dp[0] after the last cell, not the sum of all masks.
  • Blocked cells. Treat a blocked cell as "already covered" (case 1) and forbid dominoes from entering it: a vertical domino from above or a horizontal from the left must check the target cell is not blocked.
  • Overflow. 10×10 already exceeds 32 bits; JavaScript numbers lose exactness from 12×12 on. Use 64-bit, BigInt, or the modulus.
  • Odd area. Zero tilings. The DP handles it, but an early return saves time and documents intent.
  • Row-mask DP with "previous two rows". Some constraints (e.g. pieces two rows tall, or the "cannons" problem where attacks reach two cells) need the last two rows in the state: states. Then cell-by-cell with a wider frontier is often cheaper.
  • Kings: forgetting diagonal compatibility. s & t == 0 checks only vertical attacks; add s & (t << 1) and s & (t >> 1).

Variations

  • Obstacles. Blocked cells act as pre-covered cells (CSES Counting Tilings has none, but many variants do).
  • Colourings. "Colour an grid with colours, neighbours different": the profile is a base- number of digits ( states). LeetCode 1411 and 1931 are this with .
  • Ternary or richer profiles. LeetCode 1659 (Maximize Grid Happiness) stores for each frontier cell "empty / introvert / extrovert": states.
  • Plug DP (connectivity profiles). Counting Hamiltonian cycles or "single loop" configurations on a grid requires the profile to remember which frontier edges are connected to each other — encoded as a bracket sequence. Same sweep, much larger state; the technique is often called plug DP.
  • Counting with a fixed number of pieces. Add a counter dimension (Little Kings: exactly kings).
  • Transfer matrix + Berlekamp–Massey. For huge and medium , compute the first terms by DP, find the minimal linear recurrence, and jump with polynomial exponentiation.
  • Kasteleyn / Pfaffian method. Domino tilings of any planar region: count = for a signed adjacency matrix . Polynomial in the area, no width restriction.
  • Random sampling. Sample a uniformly random tiling by walking the DP backwards, or by Propp–Wilson coupling from the past for very large regions.
  • Grid DP is the 1-bit case. When the only interaction across the frontier is "the cell above/left", the profile collapses to a single number per cell: Grid & Path DP.

Practice ladder

Each problem is described in my own words; follow the link for the full statement.

1. Domino and Tromino Tiling (LeetCode 790) — Count tilings of a 2×n board with dominoes and L-trominoes, modulo . Teaches profiles for 2 rows by hand: "flat" vs "one cell sticking out".

Solution

States after column : full[i] (both cells covered up to ) and half[i] (column has one extra cell covered). full[i] = full[i-1] + full[i-2] + 2·half[i-1], half[i] = full[i-2] + half[i-1]. Eliminating half gives T(n) = 2T(n-1) + T(n-3), implemented as domino_tromino_2xn above.

2. Number of Ways to Paint N × 3 Grid (LeetCode 1411) — 3 colours, adjacent cells differ, 3 columns. Teaches row profiles as base-3 numbers (only 12 valid rows).

Solution

Enumerate the 12 valid rows (no equal neighbours) and their pairwise compatibility (no equal colour in the same column). Then a row-by-row DP.

from itertools import product


def num_of_ways(n, mod=10**9 + 7):
    rows = [r for r in product(range(3), repeat=3) if r[0] != r[1] and r[1] != r[2]]
    ok = [[all(a != b for a, b in zip(x, y)) for y in rows] for x in rows]
    dp = [1] * len(rows)
    for _ in range(n - 1):
        dp = [sum(dp[i] for i in range(len(rows)) if ok[i][j]) % mod for j in range(len(rows))]
    return sum(dp) % mod


assert num_of_ways(1) == 12
assert num_of_ways(2) == 54
assert num_of_ways(5000) == 30228214

3. Counting Tilings (CSES 2181) — Domino tilings of an board with , , modulo . Teaches exactly this lesson's DP at full scale.

Solution

The implementation above with % MOD after each addition and the mask over the side of length : steps. Sample: a 4×7 board has 781 tilings.

def counting_tilings(n, m, mod=10**9 + 7):
    if n > m:
        n, m = m, n                     # n is the short side (mask width)
    dp = [0] * (1 << n)
    dp[0] = 1
    for r in range(m):                  # sweep along the long side
        for c in range(n):
            nd = [0] * (1 << n)
            bit = 1 << c
            for mask, ways in enumerate(dp):
                if not ways:
                    continue
                if mask & bit:
                    nd[mask ^ bit] = (nd[mask ^ bit] + ways) % mod
                    continue
                if r + 1 < m:
                    nd[mask | bit] = (nd[mask | bit] + ways) % mod
                if c + 1 < n and not mask & (bit << 1):
                    nd[mask | (bit << 1)] = (nd[mask | (bit << 1)] + ways) % mod
            dp = nd
    return dp[0]


assert counting_tilings(4, 7) == 781

4. Painting a Grid With Three Different Colors (LeetCode 1931) — rows, columns, 3 colours, no equal neighbours. Teaches generating valid columns (at most 48 for ) and their compatibility graph.

Solution
from itertools import product


def color_the_grid(m, n, mod=10**9 + 7):
    cols = [c for c in product(range(3), repeat=m) if all(c[i] != c[i + 1] for i in range(m - 1))]
    nxt = [[j for j, y in enumerate(cols) if all(a != b for a, b in zip(x, y))] for x in cols]
    dp = [1] * len(cols)
    for _ in range(n - 1):
        nd = [0] * len(cols)
        for i, ways in enumerate(dp):
            for j in nxt[i]:
                nd[j] = (nd[j] + ways) % mod
        dp = nd
    return sum(dp) % mod


assert color_the_grid(1, 1) == 3
assert color_the_grid(1, 2) == 6
assert color_the_grid(5, 5) == 580986

5. Maximum Students Taking Exam (LeetCode 1349) — Seat as many students as possible on good seats so that nobody sits directly left, right, front-left or front-right of another. Teaches row masks with intra-row and diagonal compatibility.

Solution
def max_students(seats):
    n, m = len(seats), len(seats[0])
    avail = [sum(1 << j for j in range(m) if row[j] == ".") for row in seats]
    dp = {0: 0}
    for r in range(n):
        nd = {}
        for t in range(1 << m):
            if t & ~avail[r] or t & (t << 1):           # broken seat, or side-by-side
                continue
            best = None
            for s, val in dp.items():
                if s & (t << 1) or s & (t >> 1):        # diagonal from the row in front
                    continue
                best = val if best is None else max(best, val)
            if best is not None:
                nd[t] = best + bin(t).count("1")
        dp = nd
    return max(dp.values())


assert max_students([["#", ".", "#", "#", ".", "#"],
                     [".", "#", "#", "#", "#", "."],
                     ["#", ".", "#", "#", ".", "#"]]) == 4
assert max_students([[".", "#"], ["#", "#"], ["#", "."], ["#", "#"], [".", "#"]]) == 3

6. Little Kings (acm.sgu.ru 223, on Codeforces) — Count placements of exactly non-attacking kings on an board, . Teaches row masks plus a counter dimension.

Hint

dp[mask][count] over rows, valid masks without adjacent bits, compatibility with s & t, s & (t << 1), s & (t >> 1). Samples: gives 16; gives 79. Use 64-bit integers.

7. Mondriaan's Dream (POJ 2411) — The classic: count tilings of an rectangle () by 1×2 bricks, no modulus. Teaches the exact counts and 64-bit overflow awareness.

Hint

Exactly count_domino_tilings. 11×11 has odd area: 0.

8. Maximize Grid Happiness (LeetCode 1659) — Place limited numbers of introverts and extroverts on an grid () to maximise happiness that depends on each person's orthogonal neighbours. Teaches a ternary broken profile with counters.

Hint

Cell by cell; the profile stores, for the last cells, 0/1/2 (empty/introvert/extrovert) as a base-3 number. The neighbours that matter are the cell above (the oldest digit) and the cell to the left (the newest digit). State: (cell, profile, introverts left, extroverts left).

9. Number of Ways to Build Sturdy Brick Wall (LeetCode 2184) — Rows of bricks of given widths; adjacent rows may not have brick joints at the same position. Teaches row profiles as "joint positions" masks (subscription problem on LeetCode).

Hint

Enumerate all ways to fill one row and record the mask of interior joint positions. Two rows are compatible iff their masks AND to 0. Row-by-row DP over these masks.

10. Huge- tilings (self-check). Count domino tilings of a board modulo . Teaches the transfer matrix.

Hint

tilings_huge(10**18, 3) from the transfer-matrix section: an 8×8 matrix raised to the -th power in about 60 squarings.

Common mistakes & interview follow-ups

"Why does the profile need only bits?" Because a domino placed at a cell reaches at most one cell right or one cell down; both are on the staircase frontier. No cell beyond the frontier can be covered yet.

"What is 'broken' about the profile?" In cell-by-cell order, the frontier has a step at the current column: bits left of it describe the next row, bits right of it the current row.

"Row by row or cell by cell?" Cell by cell: uniform , three local cases, handles obstacles and odd pieces. Row by row: natural when constraints are between whole rows (kings, colourings, brick walls) and the valid row patterns are few.

"What if ?" Transfer matrix power: . Or Berlekamp–Massey on the first terms and a linear-recurrence jump.

"Can you do it without the width restriction?" For domino tilings, yes: Kasteleyn's Pfaffian method. For general pieces or constraints, the problem is typically #P-hard and profile DP (exponential in width) is the standard exact method.

Mistakes interviewers watch for: mask over the long side; not clearing a covered bit; allowing a horizontal domino into a covered cell; missing diagonal checks for kings; reading the answer from the wrong mask; overflow on 10×10 and larger.

Quick quiz

1. What is the number of domino tilings of a 2×7 board?

Answer

.

2. In the 3×2 trace, after cell (0,1) the vector is (1, 0, 0, 1). What do the two non-zero states mean?

Answer

Mask 00 (1 way): row 0 was covered by one horizontal domino, nothing sticks into row 1. Mask 11 (1 way): two vertical dominoes stick into row 1 at both columns.

3. Why is the answer dp[0] and not the sum over all masks?

Answer

After the last cell the frontier is the (non-existent) row . Any set bit would mean a domino sticks out of the board.

4. How many valid row transitions are there for width 4, and how does that compare with ?

Answer

29, versus 256 pairs. The counts are Pell numbers, growing like .

5. How many row masks of width 8 have no two adjacent kings?

Answer

.

6. You must count tilings of a 6× board. Roughly how big is the transfer matrix, and how many multiplications?

Answer

, so a 64×64 matrix; about 60 squarings plus up to 60 multiplications, each operations.

Further reading / sources

  • P. W. Kasteleyn, "The statistics of dimers on a lattice: I. The number of dimer arrangements on a quadratic lattice", Physica 27(12), 1961.
  • H. N. V. Temperley and Michael E. Fisher, "Dimer problem in statistical mechanics — an exact result", Philosophical Magazine 6(68), 1961.
  • H. A. Kramers and G. H. Wannier, "Statistics of the two-dimensional ferromagnet", Physical Review 60, 1941 — the transfer-matrix method.
  • Richard P. Stanley, Enumerative Combinatorics, Vol. 1, 2nd ed., Cambridge 2012 — §4.7 (the transfer-matrix method).
  • Iwan Jensen, "Enumerations of lattice animals and trees", Journal of Statistical Physics 102, 2001.
  • cp-algorithms, Dynamic Programming on Broken Profile: Problem "Parquet".
  • Antti Laaksonen, Competitive Programmer's Handbook — chapter 10 (bit manipulation, "Counting tilings").
  • OEIS A004003 (domino tilings of a board: 1, 2, 36, 6728, 12988816, …) and A001835 (3×2n tilings: 1, 3, 11, 41, 153, …).

Lessons: previous — Digit DP · next — Counting DP · module — Dynamic Programming · course — DSA: Zero to Mastery.

Related Archon pages: Bitmask DP · SOS DP · Grid & Path DP · Matrices & Grids · Bit Manipulation · Matrix Exponentiation.