The N by N Tiled Floor
Solution

When a problem has parameters of the form 2^N, it's sometimes a clue that a recursive analysis may be the proper approach.

We start out by thinking about the square being in the lower right corner. We can turn a 1 x 1 square into a 2 x 2 square:

        +---+
        | X |
        +---+
      

        +---+---+
        |       |
        +   +---+
        |   | X |
        +---+---+       
      

        +---+---+---+---+
        |       |       |
        +   +---+---+   +
        |   |       |   |
        +---+   +---+---+
        |   |   | X   X |
        +   +---+   +---+ 
        |       | X | X |
        +---+---+---+---+
      

        +---+---+---+---+
        |       |       |
        +   +---+---+   +
        |   |       |   |
        +---+   +---+---+
        |   |   |
        +   +---+ 
        |       |
        +---+---+
      

Now we use this ideas to construct a recursive solution, in which we repeatedly improve the lower right corner of the tiling, until there's nothing left. We start by simply tiling the 2 x 2 lower right section of the floor. Then we group the tiles into 2 x 2 squares, and, looked at in the right way, the problem stays the same: tile a floor using (doubled) L tiles, when there's a missing square in the lower right. But now the number of rows and columns is N-1.

This means:

• We know how to partially solve this problem too;
• Each step we take reduces the problem scale by a factor of 2;
• After N-2 size reductions, our problem is essentially the same as completing a tiling on a 2 by 2 grid with one square missing, a problem we can completely solve, thereby finishing the solution of the original problem.

Now, can we still solve the problem if the starting black square is placed arbitrarily in the grid? I think you will grant me that, whenever the black tile is the corner tile of a square whose sides are powers of 2, we can completely tile the entire square. So if the black square is in a corner, we're done. Otherwise, divide the floor by vertical and horizontal bisectors. Look at the square that contains the black tile. If the black tile is not a corner of this square, divide that square further. At some point, the black square must be a corner of a larger square (whose sides are a power of two). Then we can tile in that square. Now we can regard the square we have just tiled as a new black square, which is a corner square in a 2 x 2 square. We tile that, and repeat until we have completely tiled the floor. Hence, the initial position of the black square is unimportant. We can always complete the tiling.

Hats off to Scott Hansen of Iowa State University, for showing me this puzzle.

Back to the N by N Tiled Floor Puzzle.

Back to the 8 by 8 Tiled Floor Puzzle.