Covering a Chessboard with a Hole with L-Trominoes

Solution

Solution below is by Benjamin L. Schwartz, The MITRE Corporation, Virginia.

The problem as stated leaves unsettled the question of the existence of exactly one fault line. In the discussion below, we shall also resolve this question affirmatively with an example.

Notation. Denote the 8 horizontal rows of squares by letters A through H. Denote the vertical files by numbers 1 through 8. Denote a line between rows by the names of the two bordering rows (e.g., line BC).

1. The diagrams (1), (2), (3) and (4) show examples with zero, one, two and three fault lines, respectively. In (2), the fault line is 34. In (3), the fault lines are DE and 45; and, in (4), they are CD, EF and 45. As shown later, these arrangements of fault lines are essentially unique.

2. To prove other cases impossible, we introduce a few easily proved lemmas about coverings with trominoes. Proofs are omitted.
   1. A 2×n area can be covered iff 31 n.
   2. Two adjacent lines (e.g., CD and DE) cannot both be fault lines.
   3. A 3×3 area cannot be covered exactly.
   4. A fault line cannot occur adjacent to an edge.

Lemma IV eliminates A F, GH, 12 and 78 as candidates. But Lemma I also eliminates BC, FG, 23 and 67. Hence the only horizontal candidates are CD, DE and EF; and verticals 34, 45 and 56. Furthermore, by Lemma II, if DE is a fault line, it is the only horizontal one. Similarly, if 45 is a vertical fault line, it is the only one.

Thus, the only prospect for a 4-fault-line configuration requires that these lines be CD, EF, 34 and 56. But this means the 3×3 areas in the four corners must be covered exactly, which violates Lemma III. An additional question is whether the arrangement of fault lines in each of the various cases is essentially unique. The affirmative answer to this follows from the following theorem:

If CD is a fault line, so is EF. (Similarly 34 and 56.)

To see this, suppose there is a covering with CD as a fault line. Then consider how square Dl could be covered. Place a tromino to cover it with each of the three possible orientations of the other two squares. It follows that either the other squares of files 1 and 2 in rows D and E cannot be covered, or can only be covered in such a way as to fill exactly the 2×3 rectangle (123)×(DE). The same argument applies to (678)×(DE). Hence EF must be a fault line.

A more laborious and detailed analysis concerns the actual arrangement of the trominoes in the coverings. It has shown that except for "flipover" of the coverings of 2×3 rectangles, and rotations of the entire board, the solutions of (2), (3) and (4) are unique. A similar statement is believed to hold for (1), but has not yet been proved.