Visualizing the Defective Chessboard problem
Tags: python, programming, tutorial, algorithms
Published: 2020-01-16 05:13:12

---
title: Visualizing the Defective Chessboard problem
published: true
date: 2020-01-11 02:59:30 UTC
tags: python,programming,tutorial,algorithms
canonical_url: https://medium.com/@Polaris000/visualizing-the-defective-chessboard-problem-aa5fc38b6e5e
cover_image: https://cdn-images-1.medium.com/max/765/0*MxZqUAWFbqnmn4Ja.gif
---

![](https://cdn-images-1.medium.com/max/542/1*jMx7jrHOg4qngBL6pBp9hQ.png)<figcaption>A tiled chessboard</figcaption>

**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.

![](https://cdn-images-1.medium.com/max/528/0*adonlEHar0FeZ3XM.png)<figcaption>The board with no defects added</figcaption>

### 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.

![](https://cdn-images-1.medium.com/max/527/0*zOyl7BWBT9R4Csjd.png)<figcaption>The board in the initial state (with an added defect)</figcaption>

### 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.

![](https://cdn-images-1.medium.com/max/1024/1*fPnVzEh00aTSG3PCX2MnXQ.png)<figcaption>The Master Theorem. From <a href="https://brilliant.org/wiki/master-theorem/">brilliant.org</a></figcaption>

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

{% gist https://gist.github.com/Polaris000/c1acc2eb65190671f907bc3ce94f75c2 %}

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.

{% gist https://gist.github.com/Polaris000/8ec15b45924aedea55f6d1c21acc77aa %}

#### 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.**

{% gist https://gist.github.com/Polaris000/df8675ea720a14de8b72dfd86467cc64 %}

#### 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.

{% gist https://gist.github.com/Polaris000/4f8fdb28274d8bbd6428bc18605146f2 %}

#### 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.

{% gist https://gist.github.com/Polaris000/23f927a093660dd3cea31f8ea2a14727 %}

#### 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.

{% gist https://gist.github.com/Polaris000/77326c55f353da34b35a17667d3775cd %}

#### 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).

{% gist https://gist.github.com/Polaris000/0e823c0516d74debfb54da46e5fb2122 %}

### Visualizing

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

{% gist https://gist.github.com/Polaris000/70a9e30c4d390a78d514af461954f076 %}

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.

{% gist https://gist.github.com/Polaris000/c2ee81b82c025688e68f95e212e4288e %}

![](https://cdn-images-1.medium.com/max/765/0*MxZqUAWFbqnmn4Ja.gif)<figcaption>A GIF of the board as the algorithm runs on it</figcaption>

_Originally published at_ [_https://polaris000.github.io_](https://polaris000.github.io/blog/defective_chessboard) _on January 11, 2020._