Challenge: Larger Tiles

What if tiles are larger than $1 \times 2$? Tetrominoes ($1 \times 4$) or square tiles ($2 \times 2$)? Larger tiles mean transitions look back multiple rows.

The profile might span $2$ or more rows. State: represent the last $k$ rows, where $k$ is the tile height. State space grows to $2^{k \cdot m}$. Practical limit: $k \cdot m \leq 20$ or so. Beyond that, state space is too large. The profile depth equals the tile height. Larger tiles exponentially increase the state space.