How to solve Tiling Problem in Java

In this tutorial, we will learn how to solve a Tiling Problem in Java. Most of you already know what a Tiling Problem is, but still, I will explain it and give the basic idea behind solving such problems.

What is a Tiling Problem?

Suppose there is an area of fixed width of 2 units. Hence, n x 2 sq unit is the area, provided the length is of ‘n’ units. We have to fill the area with tiles of size 2 x 1 sq. units.
The Tiling Problem, in this case, is to find the total number of ways in which the tiles can be arranged to cover the whole area. The output will be the total number of ways, corresponding to the length of the area, given as input.

We can solve this problem by using Recursion. Though it takes a lot of time, increasing the time complexity, it usually is very helpful in solving many problems.

The Solution and the Thought Process

The given tile of size 2 x 1 can be fit in the bigger area in two ways:

1. placed vertically
2. placed horizontally

If we place it vertically, then the area left will be 2 x (n-1). So there would be (n-1) ways of filling it.

If we place it horizontally, then it will cover the area in either the top half or the bottom. But the remaining area can only be filled with another horizontal tile, thus not offering any alternative way. In this way, the total area left will be 2 x (n-2). So there would be (n-2) ways of filling it.

Thus, to get to the solution, we will have to repeat the process until we cover up the whole area. A very effective way of doing it is by Recursion.

Here is the code for the above-mentioned function.

static int numberOfWays(int 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 upper scenario where for n=0 and n=1, the answers are mentioned as 1. This is because the areas of 2 x 1 and 2 x 0 can only be filled in 1 way.

Here is the entire code.

class Tiling{
    static int numberOfWays(int c){
        if(c==0)
            return 1;
        if(c==1)
            return 1;
        return numberOfWays(c-1)+numberOfWays(c-2);             
    }
    public static void main(String args[]){
        Scanner scand = new Scanner(System.in);
        System.out.println("Enter the size of the tile board: 2 x ?");
        int b = scand.nextInt();
        
        System.out.println("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));
    }
}

Here are some sample inputs.

3
5
15

The outputs are mentioned below.

3
8
987