# 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

// HEREleft in the source file chess.cpp.

- Copy the solution program in your directory and run it.
- 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.