How to solve Tiling Problem in JavaScript

In this tutorial, we will learn how to solve the Tiling Problem in Javascript. Many of you already know what a Tiling Problem is, still I am going to explain it. We will be using Recursion to solve this problem.

What is a Tiling Problem?

Let us assume that we have a tile board with fixed width of 2 units. If the length of the board is ‘n’ units, the area of the board is n x 2 sq. unit. Let us say that we have tiles of size 2 x 1 sq. units.
The Tiling Problem asks us to find out in how many ways we can arrange these tiles to fully cover the tile board.

How to Solve the Tiling Problem?

We can arrange the tiles in two ways on the board:

  1. vertically
  2. horizontally

If the tiles are arranged vertically, it will take 2 x 1 sq. units of space, leaving 2 x (n-1) sq. units of area to be covered. So, there will be (n-1) ways in which we can arrange the tiles at that point.
If the tiles are arranged horizontally, it will take 2 x 1 sq. units of space in either the upper or lower half of the board, occupying 2 units of length. The corresponding other half can then only be covered by another horizontal tile. By doing so, the length left in the board is (n-2). Thus, we will be able to arrange the tiles in (n-2) ways at that point.

To reach the end of the board, these processes have to be repeated, so we use Recursion. It is a very useful technique, albeit a little time-consuming.

This is the code for the discussed function.

function numberOfWays(c){
  if(c==0)
    return 1;
  if(c==1)
    return 1;
  return numberOfWays(c-1) + numberOfWays(c-2);
}

Note that there are two base cases in this problem where the length can be 0 or 1. If the length is 1 unit, then the area of the board is 2 x 1 sq. units and we can arrange the tiles on it in only one way. It is also the same for when there is no length.

How to Run the file

Since this is a JavaScript code, you can run it in 3 different ways:

  1. In your browser console: Open a browser tab, click on inspect element and write the code in the console.
  2. In your Node.js terminal: If you have Node.js installed in your system, open the terminal, write Node followed by the path of the saved JavaScript file and open it.
  3. Save as HTML and open in browser: Save the code as an HTML file and open the file in a browser. Give the input in the alert box. Finally click on inspect element to check the output.

This is the full code in JavaScript.

function numberOfWays(c){
  if(c==0)
    return 1;
  if(c==1)
    return 1;
  return numberOfWays(c-1) + numberOfWays(c-2);
}

var b = prompt("Enter the size of the tile board: 2 x ?");
console.log("The total number of ways in which the tiles of size 2x1 can be used to fill a tile board of size 2x"+b+" is "+numberOfWays(b));

The following are the sample inputs.

3
5
15

These are the outputs.

3
8
987

I hope this was helpful. Thank you.

Leave a Reply

Your email address will not be published. Required fields are marked *