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.

Image for post
The board with no defects added

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.

Image for post

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.

Image for post
The Master Theorem. From brilliant.org

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

from random import randint
import matplotlib.pyplot as plt
import seaborn as sns
import numpy as np 

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.

def createboard(k):
  '''
  k: represents the size of the board.
      Number of squares on the board = 2^k * 2^k
  '''

  rows = [[] for i in range(2**k)]
  for i in range(2**k):
      rows[i] = [0] * 2**k
  return rows

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.

def add_defect(board):
  len_ = len(board)
  row = randint(0, len_ - 1)
  col = randint(0, len_ - 1)

  board[row][col] = -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.

def locate_defect(board, r1, c1, r2, c2):
  '''
  (r1, c1): row, column number of upper left square of board
  (r2, c2): row, column number of lower right square
  '''

  # find defective elem
  r = 0
  c = 0
  loc_ = []
  for i in range(r1, r2 + 1):
      loc_[:] = board[i][c1:c2 + 1]
      if -1 in loc_:
          c = loc_.index(-1) + c1
          r = i
          break
  # top
  if r <= r1 + (r2 - r1) // 2:
      # left
      if c <= c1 + (c2 - c1) // 2:
          return 0, r, c
      # right
      else:
          return 1, r, c

  # bottom
  else:
      # left
      if c <= c1 + (c2 - c1) // 2:
          return 2, r, c
      # right
      else:
          return 3, r, c

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.

def add_trionimo(board, defect, r1, c1, r2, c2):
  '''
  defect: integer between 0-3 representing which quadrant of the
      board the defect lies in.
      0: top-left
      1: top-right
      2: bottom-left
      3: bottom-right
  '''
  global num_tri
  dict_ = {
       0: (r1, c1),
       1: (r1, c2),
       2: (r2, c1),
       3: (r2, c2),
  }

  num_tri += 1
  for i in range(r1, r2 + 1):
      board[i][c1:c2+1] = [num_tri]*(r2-r1 + 1)

  rd, cd = dict_[defect]
  board[rd][cd] = -1

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.
def tile_rec(board, r1, c1, r2, c2):

  global num_tri
  # centre coordinates
  dict_ = {
          0: (r1 + (r2 - r1)//2, c1 + (c2 - c1)//2),
          1: (r1 + (r2 - r1)//2, c1 + (c2 - c1)//2 + 1),
          2: (r1 + (r2 - r1)//2 + 1, c1 + (c2 - c1)//2),
          3: (r1 + (r2 - r1)//2 + 1, c1 + (c2 - c1)//2 + 1)
      }

  # locate defect quadrant
  drawboard(board)
  defect, r, c = locate_defect(board, r1, c1, r2, c2)

  # if board size == 2 x 2
  if (r1 == r2 - 1) and (c1 == c2 - 1):
      add_trionimo(board, defect, r1, c1, r2, c2)
      return None

  else:
      # add defect to centres
      redo = True
      for value in dict_.values():
          if board[value[0]][value[1]] == 0:
              board[value[0]][value[1]] = -1
          else:
              redo = False
      if redo:
          board[dict_[defect][0]][dict_[defect][1]] = 0

      # solving the four sub-problems: each of the four quadrants
      tile_rec(board, r1, c1, r1 + (r2-r1)//2, c1 + (c2 - c1)//2),
      tile_rec(board, r1, c1 + (c2 - c1)//2 + 1, r1 + (r2-r1)//2, c2),
      tile_rec(board, r1 + (r2-r1)//2 + 1, c1, r2, c1 + (c2 - c1)//2),
      tile_rec(board, r1 + (r2-r1)//2 + 1, c1 + (c2 - c1)//2 + 1, r2, c2)

      # add last trionimo to cover defects
      num_tri += 1

      # assume that first defect was centre
      redo = True
      for value in dict_.values():
          if board[value[0]][value[1]] == -1:
              board[value[0]][value[1]] = num_tri
          else:
              redo = False
      if redo:
          board[dict_[defect][0]][dict_[defect][1]] = -1

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

def tile(board, k):
  '''
  k: represents the size of the board.
      Number of squares on the board = 2^k * 2^k
  '''

  tile_rec(board, 0, 0, 2**k - 1, 2**k - 1)
  drawboard(board)
  return board

Visualizing

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

def drawboard(board, size=(8, 8), annot=True):
    '''
    size: size of plot
    annot: if true, displays the number of the trionimo a particular
        square belongs to.
    '''

    plt.figure(figsize=size)
    sns.heatmap(board, linewidths=.1, linecolor='white',
                annot=False, cmap='magma', yticklabels=False,
                xticklabels=False, cbar=False, square=True);

    sns.heatmap(board, linewidths=.1, linecolor='white',
                annot=annot, cmap='magma', yticklabels=False,
                xticklabels=False, cbar=False, square=True,
                mask=np.array(board)<0);
    plt.show()

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.

# setting the value of k
k = 3

# setting trionimo count to 0
# this allows us to display the count on the board
num_tri = 0

# creating a board of size 2^k * 2^k
board = createboard(k)

# adding a random defect to the board
add_defect(board)

# tiling the board
board = tile(board, k)

# the tile function calls the drawboard(), allowing us
to view the state of the board at each recursive call

Image for post
A GIF of the board as the algorithm runs on it

I'm a CS Undergrad at BITS Pilani. Right now, I'm in my 4th year. I write infrequently on several topics, from technical concepts to the latest customizations on my laptop on my blog. My most interesting posts are also published on Medium.

Polaris000 – Medium
Read writing from Polaris000 on Medium. Summer Intern at Samsung Research | CS Undergrad at BITS Pilani | polaris000.github.io. Every day, Polaris000 and thousands of other voices read, write, and share important stories on Medium.