Tiling a defective chessboard

Divide and Conquer Algorithm -

Divide and conquer algorithm suggests that a larger problem be divided into smaller sub-problems and solving those smaller sub-problem and then combining those sub-problem to solve the problem altogether with much less complexity. 

We take a look at an algorithmic problem of tiling the entire chessboard where one defective tile is present.

This is the board with 1 defective tile - 

Now, we need to tile the entire board around the defective tile and make the chessboard complete.

Lets start by analyzing the mathematics of chessboard -

We often speak of chessboards in terms of area(tile in rows X tile in columns).

Example - 4 X 4, 8 X 8 etc.

So we say that the chessboards is made up of  (n X n) tiles 

1] Number of tiles in a row/column -> n = 2^k.

2] Total number of tiles in chess-board -> n X n = 2^k X 2 ^k = 2^2k.

3] Number of defective tile -> [(n X n) - 1] = (2^2k-1).

4] Lets hypothesize that ((2^2k)-1) is divisible by 3 ................(i) 

   

Testing the hypothesis by mathematical induction -

a) ((2^2k)-1)  for k=0 , it is divisible by 3.

b) ((2^2k)-1) for k=1 , it is divisible by 3.   ...............(ii)

.

.

.

.

c) substitute k=m, then for ((2^2m)-1) is divisible by 3.

d) substituting k=m+1,

    ((2^2m+2) - 1) = ((2^2 X 2^2m) - 1)

                             = (2^2 - 1) ((2^2m)-1) 

e) (2^2 - 1) is divisible by 3 and ((2^2m) -1) is divisible by 3 ...........from (i) and (ii)

Filling the tile by Triminos -

Triomino or Triomino - A triomino is a shape of polygon where 3 equal sized square are connected edge to edge with each other.

Algorithm - 

We divide the (n X n) sized chessboard into 4 halves and we introduce 1 artificial defective tile in the mini board of sized (n/2 X n/2) formed by all borders of (n X n).

The tiling then starts from around the defective tile and continues until all the chessboard is completely tiled.

Understanding the time complexity of this algorithm - 

1] The problem is first divided into 4 sub problems and size of each sub problem is n/2.

2]  Additional calculations require lets say , time complexity of O(1)

3] Therefore the time complexity becomes T(n) = 4T(n/2) + O(1)

4] By looking it through generic formula for divide and conquer recurrence,

    T(n) = aT(n/b) + f(n);

    a = 4, b = 2, f(n) = O(1).

5] comparing f(n) with O(n^log a base b)

     f(n) < O(n^2).

6] Therefor the time complexity of the algorithm becomes Theta(4^k),

     since n=2^k.

Time complexity of this algorithm is calculated by using master method which is found out to be 4^k.

In this way, the defective chessboard is tilled.