Problem
A tromping is a group of three unit squares arranged in an L-shape. Consider the following tiling problem: The input is an m × m array of unit squares where m is a positive power of 2, with one forbidden square on the array. The output is a tiling of the array that satisfies the following conditions:
Every unit square other than the input square is covered by a tromping.
No tromping covers the input square.
No two dominos overlap. No tromping extends beyond the board.
Write a divide-and-conquer algorithm that solves this problem.