Question

Give a recursive algorithm for tiling a${\mathbf{2}}^{\mathbf{n}}\mathbf{\times }{\mathbf{2}}^{\mathbf{n}}$ checkerboard with one square missing using right triominoes.

Short answer

The recursive algorithm is given

Step-by-step solution

Given that

Given a$2^{\mathrm{n}}\times 2^{\mathrm{n}}$ checkerboard with one square missing.

Write algorithm

The algorithm merely implements the idea of Example 14 in Section 5.1.

The basis step: If n= 1, then simply place the one right triomino so that its armpit corresponds to the hole in the$2\times 2$ board.

If n > 1, then divide the board into 4 boards, each of size$2^{n-1}\times 2^{n-1}$ .

Note which quarter the hole occurs in, position one right triomino at the center of the board with its armpit in the quarter where the missing square is, and invoke the algorithm recursively four times-once on each of the$2^{n-1}\times 2^{n-1}$ boards, each of which has one square missing (either because it was missing to begin with, or because it is covered by the central triomino).