Way to solve Tiling Problems

Question 1: 10359 - Tiling

Given a board of size 2×n 

                                                              

Available tiles 2×1 and 2×2

Question: Find the number of ways to completely fill the board.

E.g when n = 3 , 5ways

consider the board of width n:

How can we fill the rightmost column :

1. By one 2×1 vertically.

2. By two 2×1 horizontally.

3. By one 2×2 either horizontally or vertically( since both are same).

Let f(n) be the number of ways of filling a board of size 2×n.

So f(n) = f(n-1) + f(n-2) + f(n-2)

Now, let's determine the base cases.

1. f(0) = 1, because if we have to find f(1) then , f(1) = f(0) + f(-1) + f(-1) , since f(-1) not exist, so  f(-1) = 0 then f(1) = f(0) + 0 + 0 => f(1) = f(0) 

since there is one way to fill the board of size 2×1 by using one 2×1 tile. It means that f(0) must 

be equal to 1.

2. f(1) = 1

Code: 

Complexity: O(n)

Question 2. GNY07H - Tiling a Grid With Dominoes

Given a board of size 4×n.

Available tile 2×1

Question: Find the number of ways to completely fill the board. 

E.g when n = 2 , 5ways

consider the board of width n:

How can we fill the rightmost column:

1. By two 2×1 vertically.

2. By four 2×1 horizontally.

3. By two 2×1 horizontally in the bottom and one, 2×1 vertically in the top. 

4. By one 2×1 vertically in the bottom and two, 2×1 horizontally in the top. 

Note: Both 3 and 4 are the same, the only difference is that, the positions but the number of ways of 3 = number of ways of 4.

5. By one 2×1 horizontally in the top, one 2×1 vertically in the middle, and one 2×1 in the bottom.

Let f(n) be the number of ways of filling a board of size 4×n.

Let g(n) be the number of ways of filling a board of size 4×n of this type.

Let h(n) be the number of ways of filling a board of size 4×n of this type.

So f(n) = f(n-1) + f(n-2) + g(n-2) + g(n-2) + h(n-2)

🤓Now let's find g(n).

How can we fill the vacant 2×1 space in g(n):

1. By one 2×1 vertically, then the shape after doing this will be like f(n)

2. By adding two 2×1 horizontally, then the shape after doing this will like g(n-1)

So, g(n) = f(n) + g(n-1)

🤓Now let's find h(n).

How can we fill the vacant 2×1 space in h(n):

1. By one 2×1 vertically, then the shape after doing this will be like f(n)

2. By adding two 2×1 horizontally.

But this shape doesn't like any of  f, g or h. So we have to do something so that its shape will belong to any of f, g, or h type.

If one 2×1 horizontally on top and one 2×1 horizontally in the bottom will add, then its shape will similar to h.

So, h(n) = f(n) + h(n-2)

Now, let's determine the base cases.

1. f(0) = 1

2. f(1) = 1

3. g(0) = f(0) + g(-1) = 1 + 0 = 1

4. g(1) = f(1) + g(0) = 1 + 1 = 2

5. h(0) = f(0) + h(-2) = 1 + 0 = 1

6. h(1) = f(1) + h(-1) = 1 + 0 = 1

Code:

Complexity: O(n)

Bonus: M3TILE - LATGACH3 

Video Explanation:

Happy coding!👨‍💻