HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

3xN tiling problem with blocks of size 3x1 or 2x2

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
problemblocks2x2tilingwithsize3x13xn

Problem

I know there are a number of different tiling problems and some of them have been discussed here:
Number of ways of tiling a 3N board with 21 dominoes problem
Domino and Tromino Combined Tiling
DP tiling a 2xN tile with L shaped tiles and 2x1 tiles?.
My domain has different requirements which are as below:
https://www.codingame.com/ide/puzzle/3n-tiling

Height will be 3,
tile sizes are: 2x2, 3x1, 1x3

there are possible choices for 3x6:

┌─────┬─────┐  ┌───┬───┬───┐  ┌─────┬─────┐  ┌─┬─┬─────┬─┐
├─────┼─────┤  │   │   │   │  ├───┬─┴─┬───┤  │ │ ├─────┤ │
├─────┼─────┤  ├───┴─┬─┴───┤  │   │   │   │  │ │ ├─────┤ │
└─────┴─────┘  └─────┴─────┘  └───┴───┴───┘  └─┴─┴─────┴─┘
┌─┬─────┬─┬─┐  ┌─┬─┬─┬─────┐  ┌─────┬─┬─┬─┐  ┌─┬─┬─┬─┬─┬─┐
│ ├─────┤ │ │  │ │ │ ├─────┤  ├─────┤ │ │ │  │ │ │ │ │ │ │
│ ├─────┤ │ │  │ │ │ ├─────┤  ├─────┤ │ │ │  │ │ │ │ │ │ │
└─┴─────┴─┴─┘  └─┴─┴─┴─────┘  └─────┴─┴─┴─┘  └─┴─┴─┴─┴─┴─┘


(illustration copied from Codingame problem section).

I have come up with the following DP relation:

dp[i] = (dp[i-1] + (i >= 3 ? dp[i-3] : 0) + (i >= 6 ? dp[i-6] * 2 : 0))


dp[i-1] means at each state, you can add a 1x3 (illustration below) to previous state to get to the current state.

┌─┐
│ │
│ │
└─┘


dp[i-3] means if your width is at least 3, you can stack up three 3x1 vertically to 3 states ago (width - 3) to get to current state.

┌─────┐
├─────┤
├─────┤
└─────┘


dp[i-6] means when my width is greater than or equal to 6, I can add three 2x2 squares horizontally next to each other, then put two 3x1 rectangles on top of them to 6 states ago(width - 6), in two ways, to get to current state).

┌───┬───┬───┐  ┌─────┬─────┐ 
│   │   │   │  ├───┬─┴─┬───┤ 
├───┴─┬─┴───┤  │   │   │   │ 
└─────┴─────┘  └───┴───┴───┘


But looks like I'm missing something, my solution for 3x12 returns 124, while it should be 154.
Any help is appreciated.

Edit:

After a lot of thoughts and getting some ideas from answers, I came up with thi

Solution

Here is a systematic way to approach it. I suggest you define three values:

$A_0(n)$ is the number of ways to tile a $3 \times n$ region.

$A_1(n)$ is the number of ways to tile a $3 \times n$ region with the upper-left cell already covered.

$A_2(n)$ is the number of ways to tile a $3 \times n$ region with the upper-left cell and the cell to the right of it already covered.

Then you should be able to express each $A_i(n)$ in terms of $A_j(m)$ for $m < n$. This gives you a mutual recurrence relation for these three values. It is easy to construct these recurrent relations based on a case analysis of how the leftmost column is covered.

You can then compute these using dynamic programming, in order of increasing $m$. Or, you can substitute into each other and get a single recurrence relation for $A_0(n)$ in terms of $A_0(m)$ for $m<n$, if you prefer.

Regarding your solution:

Yeah, you're missing something. For instance, a solution could start

┌───┬───┬─────┐
│   │   ├─────┤
├───┴─┬─┴───┬─┴ 
└─────┴─────┴──


and continue from there; that won't be counted in your case analysis.

Code Snippets

┌───┬───┬─────┐
│   │   ├─────┤
├───┴─┬─┴───┬─┴ 
└─────┴─────┴──

Context

StackExchange Computer Science Q#123463, answer score: 5

Revisions (0)

No revisions yet.