# Way to solve Tiling Problems

#### 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 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)

#### 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 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)

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

Happy coding!👨💻

Great Explanation. Thanks :D

ReplyDeleteThanks :)

Delete