You are given a board of size n x n = 2^{k} x 2^{k} which has one square missing (the missing square can be at any position). Board sizes are thus 2 x 2, 4 x 4, 8 x 8, 16 x 16, 32 x 32, etc. You are given as many trominos as you need.

A tromino is an object made up of three squares:

**Show that no matter where the missing square is, the board can be tiled with trominoes!**

Note that no two trominos can overlap and every square (except the missing one) must be tiled.

The smallest board is a 2×2 board with one square missing. Any such 2×2 board can be tiled using one tromino as shown below.

In our illustrations, gray squares represent the untiled board, a white square indicates the missing square, and trominos are blue.

It is easy to convince yourself that a 2×2 board can be tiled with one tromino. It is a little harder for a 4×4 board, but the number possible locations for the missing square is still quite small. What about a board of size 1024 x 1024 = 2^{10} x 2^{10}?

Recursion will help us understand how the tiling can be generated for an arbitrary sized board. You are given a board of size 2^{k+1} x 2^{k+1 }which has one tile missing (**Figure 1**). The board consists of four boards of size 2^{k} x 2^{k} each (**Figure 2**). To figure out how to tile the board of size 2^{k+1} x 2^{k+1}, we will tile four boards of 2^{k} x 2^{k}.

Figure 1 |
Figure 2 |
Figure 3 |

Figure 4 |
Figure 5 |
Figure 6 |

We do this using recursion. Keep in mind that every time we tile a smaller board, the board **must **have one square marked as missing.

We tile a board of size 2^{k+1} x 2^{k+1} as follows:

- Conceptually split the board into four boards of size 2
^{k}x 2^{k }. (**See Figure 2**) One of the four smaller boards has a square missing. The other three boards have no squares missing. - For the smaller board with the missing tile we make a recursive call to tile it. (
**See Figure 3**) - How do we tile the remaining three smaller boards? We don’t know how to tile boards with no tile missing!
- We remove one square from each of the remaining three smaller boards – the square removed is in the ‘’center’’ of the original board. (
**See Figure 4**) - We can now make three recursive calls, each call tiling one of the three smaller boards which now each have a missing tile. (
**See Figure 5**) - The three center squares removed by us form a tromino and we place a tromino to cover them. (
**See Figure 6**)

- We remove one square from each of the remaining three smaller boards – the square removed is in the ‘’center’’ of the original board. (
- Now we are done tiling a board of size 2
^{k+1}x 2^{k+1}.

Try out the described solution – or another one – on** the interactive 8-by-8 Tromino Puzzle** at https://www3.amherst.edu/~nstarr/trom/puzzle-8by8/.