A second piece needs a second state
Track both a fully tiled board and a board with one notch left over — the extra piece needs both. About 15 minutes.
Dominoes plus L-shaped pieces
Back to tiling a 2-row floor, but now you also have L-shaped pieces that cover three squares. An L-shape can't fill a column on its own: it leaves one square of a column open, and something has to plug that gap. Two L-shapes can lock together, and dominoes can bridge between them.
That's why the simple "last column" rule from the start of this topic isn't enough any more: the floor's edge isn't always flat.
The pattern, once the gaps are tracked
Carefully tracking floors with a flat edge and floors with one corner sticking out, and how each grows by a column, boils down to one rule for flat floors: twice the answer for one column shorter, plus the answer for three columns shorter.
The count roughly doubles with every column, so for long floors it soon needs more digits than a normal number holds. Taking each result modulo 1,000,000,007 keeps the numbers small, and that's the answer the problem asks for.
full = [1, 1, 2] # n = 0, 1, 2
Small boards by hand: empty is 1 way, 2 × 1 is 1 (upright domino), 2 × 2 is 2 (two upright or two flat).
Floors of length 4, 3 and 2 can be tiled in 11, 5 and 2 ways. How many ways for length 5?
- A24
- B12
- C11
Show the answer
24. Twice the answer for length 4, plus the answer for length 2: 2 × 11 + 2 = 24.
Domino and tromino tiling
You have a 2×n board, an unlimited supply of 1×2 dominoes (upright or lying flat), and an unlimited supply of L-shaped trominoes (each covering 3 cells, in any of their 4 rotations). Return the number of distinct ways to fully tile the board, modulo 1,000,000,007.
n = 3 → 5
0 ≤ n ≤ 1,000 · return the count modulo 1,000,000,007