#### What is Tiling Problem?

In the Tiling Problem, we would be given a wall of size 4*n, which means that the wall’s height is 4 and its length is n. ( given as the input).

Now we have an endless number of little 4*1 tiles that can be put on the wall in two distinct ways. Look at the below figure for more clarity:

Our goal is to fill the entire wall with all of the possible patterns using the small tiles in any of the approaches described above.

#### Tiling Problem Solution in Python:

One can either manually implement the naive technique using loops and if-else statements or use the quicker Recursion approach. If you want to learn about recursion, just have a glance over it what the recursion is? before going to the code.

We will use recursion to divide a large problem into smaller ones. Now, let’s look at the minor problems with both arrangements.

**1st Arrangement:** The first tile is placed using **Method 1**, reducing the length of the wall by 4, and the space above the present tile can only be filled in one way ( 3 tiles according to Method 1 )

**2nd Arrangement:** Next, using **Method 2,** we may place the first tile, reducing the length of the wall by one.

After the first arrangement has been completed. We call the same method but with a lower number of n to recursively call the same operations for the remaining wall.

The ultimate solution will be the sum of the possible ways in both the arrangements in each recursive call.

## Program to Solve the Tiling Problem in Python

Recursion is used to simplify the code implementation. Just make sure you understand the solution that is given below:

### Method #1: Using Recursion (Static Input)

**Approach:**

- Give the n value as static input and store it in a variable.
- Create a recursive function say total_possiblearrangements() which accepts the given n value as an argument that returns the total number of possible arrangements in both ways.
- Inside the function, Check if the given n value is less than or equal to 3 using the if conditional statement.
- If it is true, then return 1.
- Return the value of total_possiblearrangements(gvn_n_val-1) + total_possiblearrangements(gvn_n_val-4) (Recursive Logic).
- Pass the given n value as an argument to the total_possiblearrangements() function and store it in a variable.
- Print the above result.
- The Exit of the Program.

**Below is the implementation:**

# Create a recursive function say total_possiblearrangements() which accepts the # given n value as an argument that returns the total number of possible # arrangements in both ways. def total_possiblearrangements(gvn_n_val): # Inside the function, Check if the given n value is less than or equal to 3 # using the if conditional statement. if(gvn_n_val <= 3): # If it is true, then return 1. return 1 # Return the value of total_possiblearrangements(gvn_n_val-1) + # total_possiblearrangements(gvn_n_val-4) (Recursive Logic). return total_possiblearrangements(gvn_n_val-1) + total_possiblearrangements(gvn_n_val-4) # Give the n value as static input and store it in a variable. gvn_n_val = 3 # Pass the given n value as an argument to the total_possiblearrangements() # function and store it in a variable. rslt = total_possiblearrangements(gvn_n_val) # Print the above result. print("The total number of possible arrangements in both ways = ") print(rslt)

**Output:**

The total number of possible arrangements in both ways = 1

### Method #2: Using Recursion (User Input)

**Approach:**

- Give the n value as user input using the int(input()) function and store it in a variable.
- Create a recursive function say total_possiblearrangements() which accepts the given n value as an argument that returns the total number of possible arrangements in both ways.
- Inside the function, Check if the given n value is less than or equal to 3 using the if conditional statement.
- If it is true, then return 1.
- Return the value of total_possiblearrangements(gvn_n_val-1) + total_possiblearrangements(gvn_n_val-4) (Recursive Logic).
- Pass the given n value as an argument to the total_possiblearrangements() function and store it in a variable.
- Print the above result.
- The Exit of the Program.

**Below is the implementation:**

# Create a recursive function say total_possiblearrangements() which accepts the # given n value as an argument that returns the total number of possible # arrangements in both ways. def total_possiblearrangements(gvn_n_val): # Inside the function, Check if the given n value is less than or equal to 3 # using the if conditional statement. if(gvn_n_val <= 3): # If it is true, then return 1. return 1 # Return the value of total_possiblearrangements(gvn_n_val-1) + # total_possiblearrangements(gvn_n_val-4) (Recursive Logic). return total_possiblearrangements(gvn_n_val-1) + total_possiblearrangements(gvn_n_val-4) # Give the n value as user input using the int(input()) function and store it in a variable. gvn_n_val = int(input("Enter n value = ")) # Pass the given n value as an argument to the total_possiblearrangements() # function and store it in a variable. rslt = total_possiblearrangements(gvn_n_val) # Print the above result. print("The total number of possible arrangements in both ways = ") print(rslt)

**Output:**

Enter n value = 4 The total number of possible arrangements in both ways = 2