Python Program to Solve the Tiling Problem

Python / By

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