Skip to Content

COMP333: Algorithm Theory and Design

COMP333 Algorithm Theory and Design

Practical Week 6 - Divide&Conquer

A defective chessboard is a 2^k * 2^k board of squares with exactly one defective square. When k=0, there is only one possible defective chessboard.
You are required to tile a defective chessboard using triominoes.

 -------        -------       ----            ----
 |xx|xx|        |xx|xx|       |xx|            |xx|
 -------        -------       -------      ------- 
 |xx|              |xx|       |xx|xx|      |xx|xx|
 ----              ----       -------      -------   
In this tiling two triominoes may not overlap, triominoes should not cover the defective square, and triominoes must cover all other squares. (You can verify that (2^(2k) - 1) is divisible by 3. It is quite clear you can cover a defective chessboard when k=1. A Divide and Conquer strategy leads to an elegant solution to the defective chessboard problem. A natural partitioning of a 2^k * 2^k board into four 2^{k-1} * 2^{k-1} boards. One of the four chessboards has the defect. To convert the remaining three chess boards into defective boards, we place a triomino at the corner formed by these three. Using recursion we can tile the entire defective board. The recursion terminates when the chessboard has been reduced to 1*1. The following C++ program defective_chess gives a solution to the problem (up to k=6). Your task is to write the source code of this solution by filing the missing lines
left in the source file chess.cpp.
  1. Copy the solution program in your directory and run it.
  2. Read the source program, fill the missing lines, and compile with the "-Wno-deprecated" options. The defective tile is at position [dr][dc] (for defective row and column) and marked with a 0. The variable tile allows to number each triominoes differently.