# Visualizing the Defective Chessboard problem

###
Aniruddha Karajgi
*
Originally published at
Medium
on
*
ăť6 min read

**The Defective Chessboard problem,** also known as the **Tiling Problem** is an interesting problem. It is typically solved with a âdivide and conquerâ approach. The algorithm has a time complexity of *O(nÂ˛)**.*

### The problem

Given a *n* by *n* board where *n* is of form 2^{k} where k >= 1 (Basically, n is a power of 2 with minimum value as 2). The board has one missing square). Fill the board using trionimos. A trionimo is an L-shaped tile is a 2 Ă 2 block with one cell of size 1Ă1 missing.

Solving the problem efficiently isnât the goal of this post. Visualizing the board as the algorithm runs is much more interesting in my opinion, though. Lets discuss the algorithm first.

### The Algorithm

As mentioned earlier, a divide-and-conquer (DAC) technique is used to solve the problem. DAC entails splitting a larger problem into sub-problems, ensuring that each sub-problem is an exact copy of the larger one, albeit smaller. You may see where we are going with this, but lets do it explicitly.

The question we must ask before writing the algorithm is: is this even possible? Well, yes. The total number of squares on our board is *n*Â˛, or 4^{k.} Removing the defect, we would have 4^{kâââ1,} which is always a multiple of three. This can be proved with mathematical induction pretty easily, so I wonât be discussing it.

### The base case

Every recursive algorithm must have a base case, to ensure that it terminates. For us, lets consider the case when *n*, 2^{k} is 2. We thus have a 2Ă2 block with a single defect. Solving this is trivial: the remaining 3 squares naturally form a trionimo.

### The recursive step

To make every sub-problem a smaller version of our original problem, all we have to do is add our own defects, but in a very specific way. If you take a closer look, adding a âdefectâ trionimo at the center, with one square in each of the four quadrants of our board, except for the one with our original defect would allow use to make four proper sub-problems, at the same time ensuring that we can solve the complete problem by adding a last trionimo to cover up the three pseudo-defective squares we added.

Once we are done adding the âdefectsâ, recursively solving each of the four sub-problems takes us to our last step, which was already discussed in the previous paragraph.

### The combine step

After solving each of the four sub-problems and putting them together to form a complete board, we have 4 defects in our board: the original one will lie in one of the quadrants, while the other three were those we had intentionally added to solved the problem using **DAC**. All we have to do is add a final trionimo to cover up those three âdefectsâ and we are done.

Thus, the recursive equation for time complexity becomes:

*T(n) = 4T(n/2)+c*

The **4** comes from the fact that to solve each problem of input n, we divide it into 4 sub-problems of input size *n/2* (half the length of the original board). Once we are done solving those sub-problems, all thatâs left to be done is to combine them: this is done by adding the last trionimo to cover up the pseudo-defects we added. This, of course, is done in constant time.

If you are interested in finding the asymptotic time complexity of the recurrence relation, you could try the **recursion tree method** or the **substitution method**. For now, lets just use the **Master theorem**.

The master theorem says that for a recurrence relation of the form:

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

the complexity depends on the complexities of *f(n)* and *n ^ log_b(a)* (the log is to the base *b*).

The cases in the image below tell us which case we need to use here.

Since the value of n ^ log(a) base b is *n*Â˛, while the term *f(n)* is of constant complexity, we use **Case 1,** which ultimately tells us that our algorithm has an order of ** nÂ˛**. In other words, the time complexity of our algorithm is

**O(**

*n*Â˛).### The Code

Initially, each square is represented by a 0. A â-1â represents a defective square, and would appear black in the plots. Each trionimo would be displayed with a unique number, which would be incremented as more trionimos are added.

Again, the goal of the code is not optimizationâââits to do as much from scratch (in plain python) as possible.

I have commented the code below, so it should be pretty straight-forward.

#### Importing required libraries

The random library is used to randomly pick a square to be defective, just for starting the problem, and seaborn is, of course, for the visualization.

#### Creating the board

Nothing too crazy: just creating a two dimensional Python list. The algorithm can be optimized by using structures like numpy arrays instead of vanilla Python lists. The list is initialized with 0's.

#### Adding a defect randomly

Here we are randomly choosing an element using randint() and making it the defective tile. We will represent defects with a **-1.**

#### Locating the defect when solving each sub-problem

We are doing two things here:

- locating the row and column of the defect
- determining which quadrant of the board the defect lies in

The first step can be optimized by using numpy functions instead of the âfrom-scratchâ approach below.

#### Adding trionimos

This function adds a trionimo to a 2 x 2 section of the board. Here, the quadrant of the defect comes in handy as we can simply define a dictionary to decide how to add our trionimo.

#### Recursive Tiling Function

This is a divide-and-conquer implementation of our tiling algorithm. The function accomplishes the following:

- determining the location of the defect in the given section of the board (the rows r1 and r2 and the columns c1 and c2 allow the function to focus on a particular section of the board).
- adding a trionimo if we are dealing with a 2 x 2 section of the board
- otherwise, adding three defects to the center
- recursively solving each quadrant of the board
- adding a final trionimo to cover up the three defects we added at the center.

#### The Parent Tiling Function

This just makes the interface cleaner since we technically have only two independent arguments: the board and the parameter k (well, k can be calculated or used as a global variable, but thatâs up to the programmer).

### Visualizing

I made use of a simple **seaborn heat-map** to display the board. The drawboard() method creates the heat-map.

The two heat-map calls are to more easily distinguish between defective and non-defective squares:

- the first one creates the heat-map without any labels or masks.
- the second heat-map has a mask which hides the defective squares, but annotates the rest, allowing us to distinguish each trionimo by number while leaving defective squares blank.

### The result

Iâve dragged the post long enough. The snippet below calls relevant functions, allowing us to view each of the boardâs states.

*Originally published at* *https://polaris000.github.io* *on January 11, 2020.*