Detailed mathematical approach

Problem Summary

The task is to count the number of tilings of a \(9\times12\) rectangle by triominoes. The implementations allow all six orientations: the two straight trominoes and the four \(L\)-shaped trominoes.

Because each piece covers exactly three cells, the obvious necessary condition is \(3 \mid 9\cdot12\), so the challenge is not existence but exact enumeration. A direct search is still hopeless, since a local choice can affect cells one or two rows later.

Mathematical Approach

A moving three-row frontier with a two-row stored profile

Process the board from top to bottom. At any stage, the dynamic program remembers which cells are already occupied in two consecutive frontier rows. A bit value of 1 means that the cell is already covered by pieces chosen earlier, and a bit value of 0 means that the cell must still be completed by pieces extending farther downward.

The stored state therefore needs only \(2W\) bits for width \(W\). During one transition, a fresh third row is attached underneath those two rows, so the local search works on a temporary \(3W\)-bit mask. When that search finishes, the oldest row is dropped and the remaining two rows become the next stored profile.

This is the key compression: the global tiling is huge, but all future decisions depend only on the occupancy pattern of the next two rows.

The six legal placements around the current frontier cell

The recursive search scans the newly attached bottom row from right to left. For the current column \(c\), every new piece is charged to the cell \((r+2,c)\), the lowest cell of that placement inside the three-row window. Relative to rows \(r,r+1,r+2\), the six admissible shapes are

$\begin{aligned} &\{(r,c),(r+1,c),(r+2,c)\},\\ &\{(r+2,c-2),(r+2,c-1),(r+2,c)\},\\ &\{(r+1,c),(r+2,c-1),(r+2,c)\},\\ &\{(r+1,c-1),(r+2,c-1),(r+2,c)\},\\ &\{(r+1,c-1),(r+1,c),(r+2,c)\},\\ &\{(r+1,c),(r+1,c+1),(r+2,c)\}. \end{aligned}$

These are exactly the two straight triominoes and the four rotations of the \(L\)-triomino. There is also a “skip” branch in the DFS: if \((r+2,c)\) was already covered by a placement chosen at a larger column, the search simply moves left.

Transfer recurrence on profiles

Let \(S\) be the set of all \(2W\)-bit profiles, and let \(T(s,t)\) be the number of local completions that start from stored profile \(s\), add pieces whose lowest cells lie in the new row, and end with next profile \(t\).

If \(F_k(s)\) denotes the number of ways to process the first \(k\) board rows and finish with profile \(s\), then the row-to-row transition is

$F_{k+1}(t)=\sum_{s\in S} F_k(s)\,T(s,t).$

The crucial validity condition is that the oldest of the three rows must be completely filled at the end of the local search. No later piece can reach that far upward, so any unfinished cell there would make the whole partial tiling impossible.

Worked example: repairing holes from one row below

Take width \(W=4\). Suppose the current stored profile is 1111 | 0110: the older row is already complete, while in the next row only the two middle cells are covered. The newly appended third row starts as 0000.

Now place an \(L\)-triomino on the left covering \((r+1,0),(r+2,0),(r+2,1)\), and a mirrored \(L\)-triomino on the right covering \((r+1,3),(r+2,2),(r+2,3)\). After those two placements the three rows become 1111, 1111, 1111.

So this local completion is valid, and after dropping the oldest row the next stored profile is again 1111 | 1111. This shows why a hole in the second frontier row is not yet fatal: it may be completed by a piece whose lowest cell lies in the new row.

Boundary conditions

Let \(\mathbf{1}\) denote the profile whose two stored rows are completely filled. The dynamic program starts from \(F_0(\mathbf{1})=1\). That encodes the top boundary: nothing may protrude above the rectangle, so the two fictitious rows above the board are treated as already closed.

After all \(H\) actual rows have been processed, the answer is \(F_H(\mathbf{1})\). Ending at the full profile means that no unfinished triomino protrudes below the bottom edge. For Problem 161, the implementations evaluate this at \(W=9\) and \(H=12\).

How the Code Works

State storage and row updates

The C++, Python, and Java implementations all perform the same row-by-row dynamic program. A profile is encoded as a bitmask for two frontier rows. The C++ and Java versions keep dense arrays indexed by that mask, while the Python version stores only the currently reachable masks in dictionaries.

Each DP layer represents one more processed row. For every active profile, the implementation enumerates all valid local completions of the three-row window, counts how many times each next profile occurs, and adds that multiplicity to the next layer.

Enumerating local completions

The local enumeration is a depth-first search over the columns of the new row. It tries the six geometric placements above whenever their required cells are still free and their columns stay inside the board. When the search reaches the left end, it accepts the transition only if the oldest frontier row is fully occupied; the next profile is then obtained by discarding that row and shifting the remaining mask down by one row.

The Python implementation caches the transition list for every profile that it has already explored. The C++ and Java implementations recompute those transfers as needed but use fixed-size integer arrays for fast accumulation. Despite those engineering differences, all three programs realize the same transfer matrix.

Complexity Analysis

For width \(W\), the stored state space has size \(2^{2W}=4^W\). In Problem 161, \(W=9\), so there are at most \(2^{18}=262{,}144\) possible profiles, although many of them are never reachable.

For each active profile, transition generation is a bounded DFS over at most \(W\) columns with only local branching from the six triomino placements and the skip case. Thus the method is exponential in the narrow dimension \(W\), but linear in the height once transitions are available. This is exactly the regime where profile DP is effective.

The dense-array implementations use \(O(2^{2W})\) memory for the current and next layers. The Python version stores fewer profiles at once, but it still traverses the same underlying state graph.

Footnotes and References

1. Project Euler 161: https://projecteuler.net/problem=161
2. Tromino: Wikipedia - Tromino
3. Polyomino: Wikipedia - Polyomino
4. Transfer-matrix method: Wikipedia - Transfer-matrix method
5. Profile dynamic programming: cp-algorithms - Dynamic Programming on Broken Profile