patternMinor
3xN tiling problem with blocks of size 3x1 or 2x2
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:
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
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.
$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.