PD4CS

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¹⁰ x 2¹⁰?

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)
• 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/.