Tiling Problem Using Divide and Conquer Algorithm

Shreya Deep
Last Updated: Jun 30, 2022
Difficulty Level :
MEDIUM

Introduction

The Divide and Conquer algorithm (or DAC) solves a huge task or a problem by breaking it into smaller sub-tasks or sub-problems; after solving, we combine all the sub-tasks in a specific manner we get the result for the big task.

Let's see a problem whose solution is based on this algorithm. (Also see Data Strucutres)

Problem Statement

Consider a board of size n*n, where n = 2^k and k>=1. One cell of size 1x1 is missing from the board. The task is to fill the board using L-shaped tiles. An L-shaped tile is like this:

Board

It is a 2x2 board with one 1x1 cell missing.

Input format:

In the input, you will be given the value of n and a 2D array, "board." In the array board, the missing cell has the value -1, and all the other cells have a value of 0. 

Output format:

You have to fill the board's cells with numbers such that three cells with the same number are part of one L-shaped tile.

For example,

Input

n = 4

board =

Board cells filled with numbers

Output

Final Output

Solution Approach

This problem is solved using the Divide and conquer approach. The idea is that we can fill a 2x2 board with one missing cell easily. We can place a tile over it because it is an L-shaped board only. Thus, the problem for the 2x2 board is solved. (Refer to the image below)

L- shaped board

In the above figure, the black cell is the missing cell, and we fill the rest of the cell using an L-shaped tile, and we're done.

How do we solve the original problem for an nxn size board?

  • Since n is a power of 2, i.e., n = 2^k (where, k>=1), if we keep dividing the board into smaller boards of half the size of the original board, after some divisions, we can convert the original board into 2^(2k-2) boards of size 2x2. 
  • For example, we divide the below 8x8 board into 16 2x2 boards.
     
Ilustration
  • If you notice, this is nothing but Divide and conquer approach. Here, we have a base case (2x2 board by 1 L-shaped tile) whose answer we know, and dividing the original bigger case into smaller cases can help us reach the base case.


One point to focus on is that:

When we divide an nxn board into boards of size (n/2)x(n/2) size, we will get four boards of (n/2)x(n/2) size. But, will these boards be identical? 

The answer is no. Because one of the boards will have a missing cell and the others won't have. Since we want four identical boards, we also have to remove one cell from the other three boards. We can do this by placing an L-shaped tile at the centre of the original nxn board such that it doesn't cover the quadrant that contains the missing cell (refer to the image below). Now, all the four boards of size (n/2)x(n/2) will have one missing cell (a cell that doesn't need to be filled).

Illustration

In this case, we can see that all the four sub-boards have one cell, which we don't need to fill. Thus, all 4 boards are now identical.

By dividing the (n/2)x(n/2) cells further several times similarly, we will get 2x2 boards. Thus, we will be able to solve the whole problem. After filling, the 8x8 board will look like this:

Ilustration

The black cell is the missing cell in the above figure, and the rest of them are filled using L-shaped tiles.

The steps of implementation are:

  • Input the value of n and the board.
     
  • Call the recursive function "func", which fills the board. In the function "func":
    • Declare variables that will store the row number and column number of the missing cell
       
    • Write the base case. The base case is that if n==2, we place an L in the 2x2 board, such that it covers all the three cells which are not filled. We will fill the board with a new tile, thus increasing the tile number by 1. Fill all the tiles other than the missing tile.
       
    • Else, find the missing cell's row and column. The cell whose value is -1 is the missing cell.
       
    • Now, since we've found the missing cell, we need to fill the other three sub-board quadrants which don't have the missing cell using an L. For doing this, we have another "fill" function.
       
    • If the missing tile is in the 1st quadrant, call the fill function for the second, third, and fourth quadrants. This "fill" function fills the corners of the three quadrants using an L. Thus, increase the tile number each time we call it. 
       
    • If the missing tile is in the third quadrant, call the fill function for the second, first, and fourth quadrants.
       
    • If the missing tile is in the second quadrant, call the fill function for the first, third, and fourth quadrants.
       
    • If the missing tile is in the fourth quadrant, call the fill function for the second, third, and first quadrants.
       
    • Now that we have four sub-boards, call the function "func" for the four sub-boards.
       
  • Print the board in the end.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;

int tile_number = 0;

// Function to fill the corners of the three sub-boards 
// which don't contain the missing cell
void fill(int x1, int y1, int x2, int y2, int x3, int y3, vector<vector<int>> &board)
{
    tile_number++;
    board[x1][y1] = tile_number;
    board[x2][y2] = tile_number;
    board[x3][y3] = tile_number;
}

// Function for filling the board
void func(int n, int r, int c, vector<vector<int>> &board)
{
    // Declares variables which will store the 
    // row number and column number of the missing cell
    int missing_cell_row, missing_cell_col;
    // Base case
    //  If the board size is 2
    if (n == 2)
    {
        // We will fill the board with a new tile, 
        // thus increase the tile number by 1 
        tile_number++;
        // Fill all the tiles other than the missing tile
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (board[r + i][c + j] == 0)
                {
                    board[r + i][c + j] = tile_number;
                }
            }
        }
        return;
    }
    else
    {
        // Find the missing cell's row and column
        for (int i = r; i < r + n; i++)
        {
            for (int j = c; j < c + n; j++)
            {
                if (board[i][j] != 0)
                      // The cell whose value is 
                        // not 0 is the missing cell
                        missing_cell_row = i,
                        missing_cell_col = j;
            }
        }
    }
    // If missing tile is in the 1st quadrant
    if (missing_cell_row < r + n / 2 && missing_cell_col < c + n / 2)
    {
        fill(r + n / 2, c + (n / 2) - 1, r + n / 2, c + n / 2, r + n / 2 - 1, c + n / 2, board);
    }

    // If missing tile is in the 3rd quadrant
    else
         if (missing_cell_row >= r + n / 2 && missing_cell_col < c + n / 2)
        {
            fill(r + (n / 2) - 1, c + (n / 2), r + (n / 2), c + n / 2, r + (n / 2) - 1, c + (n / 2) - 1, board);
        }

    // If missing tile is in the 2nd quadrant
    else  if (missing_cell_row < r + n / 2 && missing_cell_col >= c + n / 2)
    {
        fill(r + n / 2, c + (n / 2) - 1, r + n / 2, c + n / 2, r + n / 2 - 1, c + n / 2 - 1, board);
    }

    // If missing Tile is in 4th quadrant
    else  if (missing_cell_row >= r + n / 2 && missing_cell_col >= c + n / 2)
    {
        fill(r + (n / 2) - 1, c + (n / 2), r + (n / 2), c + (n / 2) - 1, r + (n / 2) - 1, c + (n / 2) - 1, board);
    }

    // call the recursive function for the 4 sub-boards
    func(n / 2, r, c + n / 2, board);
    func(n / 2, r, c, board);
    func(n / 2, r + n / 2, c, board);
    func(n / 2, r + n / 2, c + n / 2, board);

    return;
}

int main()
{
    int n = 4;
    vector<vector<int>> board = {
        {0, 0, 0, 0},
        {0, - 1, 0, 0},
        {0, 0, 0, 0},
        {0, 0, 0, 0}};
     
    
    func(n, 0, 0, board);
      // Call the function to fill the board
        // Print the filled board in the end
        for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cout << board[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

 

Input

4
0 0 0 0 
0 -1 0 0 
0 0 0 0
0 0 0 0

 

Output

3 3 2 2
3 -1 1 2
4 1 1 5
4 4 5 5

Implementation in Java

import java.util.*;
import java.lang.*;
import java.io.*;

class Solution{
    public static int tile_number = 0;
    // Function to fill the corners of the three sub-boards 
    //which don't contain the missing cell
    public static void fill(int x1, int y1, int x2, int y2, int x3, int y3, ArrayList<ArrayList<Integer>> board){
        tile_number++;
        board.get(x1).set(y1, tile_number);
        board.get(x2).set(y2, tile_number);
        board.get(x3).set(y3, tile_number);
    }
    
    // Function for filling the board
    public static void func(int n, int r, int c, ArrayList<ArrayList<Integer>> board, int missing_cell_row, int missing_cell_col){

        //Base case
        // If the board size is 2
        if(n==2){
            // We will fill the board with a new tile, 
            // thus increase the tile number by 1 
            tile_number++;
            // Fill all the tiles other than the missing tile
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (board.get(r + i).get(c + j) == 0) {
                        board.get(r + i).set(c + j, tile_number);
                    }
                }
            }
            return;
        }
    
        // If missing tile is in the 1st quadrant
        if (missing_cell_row < r + n / 2 && missing_cell_col < c + n / 2){
            fill(r + n / 2, c + (n / 2) - 1, r + n / 2, c + n / 2, r + n / 2 - 1, c + n / 2,board);
        }
     
        // If missing tile is in the 3rd quadrant
        else if (missing_cell_row >= r + n / 2 && missing_cell_col < c + n / 2){
            fill(r + (n / 2) - 1, c + (n / 2), r + (n / 2), c + n / 2, r + (n / 2) - 1, c + (n / 2) - 1,board);
        }
     
        // If missing tile is in the 2nd quadrant
        else if (missing_cell_row < r + n / 2 && missing_cell_col >= c + n / 2){
            fill(r + n / 2, c + (n / 2) - 1, r + n / 2, c + n / 2, r + n / 2 - 1, c + n / 2 - 1,board);
        }
     
        // If missing Tile is in 4th quadrant
        else if (missing_cell_row >= r + n / 2 && missing_cell_col >= c + n / 2){
            fill(r + (n / 2) - 1, c + (n / 2), r + (n / 2), c + (n / 2) - 1, r + (n / 2) - 1, c + (n / 2) - 1,board);
        }
     
        // call the recursive function for the 4 sub-boards
        func(n/2, r, c + n / 2,board, missing_cell_row, missing_cell_col);
        func(n/2, r, c,board, missing_cell_row, missing_cell_col);
        func(n/2, r + n / 2, c,board, missing_cell_row, missing_cell_col);
        func(n/2, r + n / 2, c + n / 2,board, missing_cell_row, missing_cell_col);
    
        return;
    }
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		int n=4;
        ArrayList<ArrayList<Integer>> board = new ArrayList<ArrayList<Integer>>();
        board.add(new ArrayList<Integer>(Arrays.asList(0, 0, 0, 0)));
        board.add(new ArrayList<Integer>(Arrays.asList(0, -1, 0, 0)));
        board.add(new ArrayList<Integer>(Arrays.asList(0, 0, 0, 0)));
        board.add(new ArrayList<Integer>(Arrays.asList(0, 0, 0, 0)));

        func(n,0,0,board, 1, 1); // Call the function to fill the board
        // Print the filled board in the end
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                System.out.print(board.get(i).get(j)+" ");
            }
            System.out.println();
        }
	}
}

 

Input

4
0 0 0 0 
0 -1 0 0 
0 0 0 0
0 0 0 0

 

Output

3 3 2 2
3 -1 1 2
4 1 1 5
4 4 5 5

Implementation in Python

tile_number = int(0)

# Function to fill the corners of the three sub-boards 
# which don't contain the missing cell
def fill(x1, y1, x2, y2, x3, y3, board):
    global tile_number
    tile_number+=1
    board[int(x1)][int(y1)] = tile_number
    board[int(x2)][int(y2)] = tile_number
    board[int(x3)][int(y3)] = tile_number

# Function for filling the board
def func(n, r, c, board):
    n = int(n)
    r = int(r)
    c = int(c)
    # Declares variables which will store the 
    # row number and column number of the missing cell
    missing_cell_row,missing_cell_col = 0, 0
    # Base case
    # If the board size is 2
    if(n==2):
        global tile_number
        # We will fill the board with a new tile, 
        # thus increase the tile number by 1 
        tile_number+=1
        # Fill all the tiles other than the missing tile
        for i in range(n):
            for j in range(n):
                if (board[int(r + i)][int(c + j)] == 0):
                    board[int(r + i)][int(c + j)] = tile_number
        return
    else:
        # Find the missing cell's row and column
        for i in range(r, r+n):
            for j in range(c, c+n):
                if (board[i][j] is not 0): #The cell whose value is 
                    # not 0 is the missing cell
                    missing_cell_row, missing_cell_col = i, j
                    
    # If missing tile is in the 1st quadrant
    if (missing_cell_row < r + n / 2 and missing_cell_col < c + n / 2):
        fill(r + n / 2, c + (n / 2) - 1, r + n / 2, c + n / 2, r + n / 2 - 1, c + n / 2,board)
 
    # If missing tile is in the 3rd quadrant
    elif (missing_cell_row >= r + n / 2 and missing_cell_col < c + n / 2):
        fill(r + (n / 2) - 1, c + (n / 2), r + (n / 2), c + n / 2, r + (n / 2) - 1, c + (n / 2) - 1,board)
 
    # If missing tile is in the 2nd quadrant
    elif (missing_cell_row < r + n / 2 and missing_cell_col >= c + n / 2):
        fill(r + n / 2, c + (n / 2) - 1, r + n / 2, c + n / 2, r + n / 2 - 1, c + n / 2 - 1,board)

 
    # If missing Tile is in 4th quadrant
    elif (missing_cell_row >= r + n / 2 and missing_cell_col >= c + n / 2):
        fill(r + (n / 2) - 1, c + (n / 2), r + (n / 2), c + (n / 2) - 1, r + (n / 2) - 1, c + (n / 2) - 1,board)
 
    # call the recursive function for the 4 sub-boards
    func(n/2, r, c + n / 2,board)
    func(n/2, r, c,board)
    func(n/2, r + n / 2, c,board)
    func(n/2, r + n / 2, c + n / 2,board)


n = int(4)
board = [[0, 0, 0, 0],
        [0, -1, 0, 0],
        [0, 0, 0, 0],
        [0, 0, 0, 0]]
    
func(n,int(0),int(0),board) #Call the function to fill the board
# Prthe filled board in the end
for i in range(n):
    for j in range(n):
        print(str(int(board[i][j])), end = " ")
    print()

 

Input

4
0 0 0 0 
0 -1 0 0 
0 0 0 0
0 0 0 0

 

Output

3 3 2 2
3 -1 1 2
4 1 1 5
4 4 5 5

Complexity Analysis

Time complexity:

O(n^2), where n is the size of the board

Reason: The recurrence relation in this solution is T(n) = 4T(n/2) + C. Thus, using the master method, the time complexity will be O(n^2). 

 

Space complexity:

O(n^2), where n is the size of the board

Reason: We have not taken any extra space in the solution. The only space taken is by the recursion stack. Since the number of 2x2 boards will be 2^(2k-2) where n = 2k, the space taken by the recursion stack will be 2^(2k-2), which can be written as n^2.

Frequently Asked Questions

What are the Divide and Conquer algorithm?

The Divide and Conquer algorithm (or DAC) is an algorithm that solves a very big task or a problem by breaking it into smaller sub-tasks or sub-problems; after solving, we combine all the sub-tasks in a specific manner so that we get the result for the big task.

What is the difference between Divide and Conquer and Dynamic Programming (DP)?

The DAC algorithm and DP (or Memoization) divide a big task into smaller sub-tasks. But the major difference between these two is that the DP algorithm saves the result of the sub-problems to be utilized in the future, but in the case of DAC, the sub-tasks are further solved recursively and are not saved for future reference.

What are the disadvantages of the divide and conquer algorithm?

Some disadvantages of the Divide and conquer algorithm are:

  • Most of the algorithms that use the DAC approach are implemented using recursion, making them costly in memory management.
  • Stack space for recursive calling increases the space complexity.
  • The DAC approach is challenging to implement when the sub-problems are not similar.

Conclusion

This article discussed the solution to the tiling problem using the Divide and conquer algorithm. To solve more problems on the Divide and conquer algorithm, you should go to CodeStudio. If you want to understand the divide and conquer algorithm and where it is used, check out Divide and Conquer Notes in Guided Paths. Some of the problems are Count InversionsLongest common prefixReverse pairsMedian of two sorted arraysWrong turn, and Ninjas and ladoos.  Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? Attempt our Online Mock Test Series on CodeStudio now!

Happy Coding!

Was this article helpful ?
0 upvotes