In: Computer Science
6. A tromino is a group of three unit squares arranged in an
L-shape. In the following tiling problem, the input is an n by n
array of unit squares where n = 2k for some positive integer k,
with one forbidden square in the array. You want to generate a
tiling of the array satisfying the following conditions: (a) every
square other than the forbidden square is covered by a tromino
(this means that the forbidden square is not covered); (b) no two
trominos overlap; and (c) no tromino extends beyond the array.
Design a divide-and-conquer algorithm that solves the tiling
problem.