{"id":25702,"date":"2021-12-04T09:19:23","date_gmt":"2021-12-04T03:49:23","guid":{"rendered":"https:\/\/python-programs.com\/?p=25702"},"modified":"2021-12-04T09:19:23","modified_gmt":"2021-12-04T03:49:23","slug":"python-program-to-solve-the-tiling-problem","status":"publish","type":"post","link":"https:\/\/python-programs.com\/python-program-to-solve-the-tiling-problem\/","title":{"rendered":"Python Program to Solve the Tiling Problem"},"content":{"rendered":"
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).<\/p>\n
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:<\/p>\n
<\/p>\n
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.<\/p>\n
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.<\/p>\n
We will use recursion to divide a large problem into smaller ones. Now, let’s look at the minor problems with both arrangements.<\/p>\n
1st Arrangement:<\/strong> The first tile is placed using Method 1<\/strong>, 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 ) 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.<\/p>\n The ultimate solution will be the sum of the possible ways in both the arrangements in each recursive call.<\/p>\n Recursion is used to simplify the code implementation. Just make sure you understand the solution that is given below:<\/p>\n Approach:<\/strong><\/p>\n Below is the implementation:<\/strong><\/p>\n Output:<\/strong><\/p>\n Approach:<\/strong><\/p>\n Below is the implementation:<\/strong><\/p>\n Output:<\/strong><\/p>\n <\/p>\n <\/p>\n","protected":false},"excerpt":{"rendered":" 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 …<\/p>\n
\n2nd Arrangement:<\/strong> Next, using Method 2,<\/strong> we may place the first tile, reducing the length of the wall by one.<\/p>\nProgram to Solve the Tiling Problem in Python<\/h2>\n
\n
Method #1: Using Recursion (Static Input)<\/h3>\n
\n
# Create a recursive function say total_possiblearrangements() which accepts the\r\n# given n value as an argument that returns the total number of possible\r\n# arrangements in both ways.\r\n\r\n\r\ndef total_possiblearrangements(gvn_n_val):\r\n # Inside the function, Check if the given n value is less than or equal to 3\r\n # using the if conditional statement.\r\n\r\n if(gvn_n_val <= 3):\r\n # If it is true, then return 1.\r\n return 1\r\n # Return the value of total_possiblearrangements(gvn_n_val-1) +\r\n # total_possiblearrangements(gvn_n_val-4) (Recursive Logic).\r\n return total_possiblearrangements(gvn_n_val-1) + total_possiblearrangements(gvn_n_val-4)\r\n\r\n\r\n# Give the n value as static input and store it in a variable.\r\ngvn_n_val = 3\r\n# Pass the given n value as an argument to the total_possiblearrangements()\r\n# function and store it in a variable.\r\nrslt = total_possiblearrangements(gvn_n_val)\r\n# Print the above result.\r\nprint(\"The total number of possible arrangements in both ways = \")\r\nprint(rslt)\r\n<\/pre>\n
The total number of possible arrangements in both ways = \r\n1<\/pre>\n
Method #2: Using Recursion (User Input)<\/h3>\n
\n
# Create a recursive function say total_possiblearrangements() which accepts the\r\n# given n value as an argument that returns the total number of possible\r\n# arrangements in both ways.\r\n\r\n\r\ndef total_possiblearrangements(gvn_n_val):\r\n # Inside the function, Check if the given n value is less than or equal to 3\r\n # using the if conditional statement.\r\n\r\n if(gvn_n_val <= 3):\r\n # If it is true, then return 1.\r\n return 1\r\n # Return the value of total_possiblearrangements(gvn_n_val-1) +\r\n # total_possiblearrangements(gvn_n_val-4) (Recursive Logic).\r\n return total_possiblearrangements(gvn_n_val-1) + total_possiblearrangements(gvn_n_val-4)\r\n\r\n\r\n# Give the n value as user input using the int(input()) function and store it in a variable.\r\ngvn_n_val = int(input(\"Enter n value = \"))\r\n# Pass the given n value as an argument to the total_possiblearrangements()\r\n# function and store it in a variable.\r\nrslt = total_possiblearrangements(gvn_n_val)\r\n# Print the above result.\r\nprint(\"The total number of possible arrangements in both ways = \")\r\nprint(rslt)\r\n<\/pre>\n
Enter n value = 4\r\nThe total number of possible arrangements in both ways = \r\n2<\/pre>\n