The Mutilated Chessboard, math that surprises you lesson

Cut two diagonally opposite corner squares off an 8 by 8 chessboard and 62 squares remain. A domino covers two squares that share a side, so 31 dominoes have exactly the right total area. Can they cover the board with no overlaps and nothing hanging over the edge? This page answers the question for every possible arrangement at once by watching a single color count, and then looks at what changes when other squares are removed.

Key terms

Mutilated chessboard problem

Definition Number the rows and the columns of an 8 by 8 chessboard from $1$ to $8$ , and color the square in row $r$ and column $c$ black when $r + c$ is even and white when it is odd, which gives the usual alternating pattern. The mutilated chessboard problem removes the two diagonally opposite corners $(1, 1)$ and $(8, 8)$ and asks whether $31$ dominoes can cover the remaining $62$ squares. Each domino is a $1$ by $2$ rectangle lying on exactly two squares of the board that share a side, no two dominoes overlap, and no domino covers a removed square or reaches past the edge. The answer is no. Two squares that share a side lie in the same row with columns differing by $1$ , or in the same column with rows differing by $1$ , so their sums $r + c$ differ by $1$ and the squares have opposite colors. Every domino therefore covers one black and one white square, and $31$ dominoes would cover $31$ squares of each color. Both removed corners are black, since $1 + 1$ and $8 + 8$ are even, so the board has only $30$ black squares and $32$ white ones.

In plain words The total area fits, but the colors do not. Every domino needs one square of each color, and the two missing corners have the same color, so the board runs two squares short of one color.

Example Each row of the full board alternates colors and has $4$ squares of each, so the full board has $32$ black and $32$ white squares. Removing the two black corners leaves

\begin{aligned} \text{black} &= 32 - 2 = 30, \\[0.4em] \text{white} &= 32. \end{aligned}

A covering by $31$ dominoes would need $31$ squares of each color, so two white squares would always be left without a black partner. Trying arrangements one at a time by hand would be hopeless, since the full board alone has $12{,}988{,}816$ different domino tilings. The color count rules out every arrangement on the mutilated board at once.

Domino tiling

Definition A region is a set of squares of a grid. A domino tiling of a region is a collection of dominoes, each lying on two squares of the region that share a side, such that every square of the region is covered by exactly one domino. So the dominoes leave no gaps, do not overlap and stay inside the region. A region of $N$ squares can have a domino tiling only if $N$ is even, and then every tiling of it uses exactly $N/2$ dominoes.

In plain words Cover every square exactly once with pieces two squares long that lie along the grid lines.

Example The full board has a tiling with four horizontal dominoes in every row. Remove instead the two squares in row $1$ and columns $1$ and $2$ . Row $1$ keeps the six squares in columns $3$ to $8$ , which take three horizontal dominoes, and the other seven rows take four each, so $3 + 28 = 31$ dominoes tile the board. If the removed squares are in row $1$ and columns $2$ and $3$ , horizontal dominoes alone cannot work, because the square $(1, 1)$ is cut off from the rest of its row. A tiling still exists. Pair $(1, 1)$ with $(2, 1)$ and $(1, 8)$ with $(2, 8)$ , cover columns $4$ to $7$ of row $1$ with two horizontal dominoes and columns $2$ to $7$ of row $2$ with three, and fill rows $3$ to $8$ with four horizontal dominoes each.

Invariant

Definition An invariant of a process is a quantity or property that has the same value after every allowed step as it had before the step. If an invariant has different values at a starting state and at a target state, then no sequence of allowed steps, however long, leads from the start to the target. An invariant can only show that a target is out of reach. When its values at the start and the target agree, it says nothing about whether the target can be reached.

In plain words Find something that no legal move can change. If it differs between where you are and where you want to be, you can never get there.

Example Place dominoes on the mutilated board one at a time, each on two uncovered squares that share a side, and let $D$ be the number of uncovered white squares minus the number of uncovered black squares. At the start

D = 32 - 30 = 2.

Each domino covers one square of each color, so both counts drop by $1$ and $D$ stays $2$ . A fully covered board would have $D = 0 - 0 = 0$ , so it is never reached. The number of uncovered squares is not an invariant, since it drops by $2$ at every step. Whether that number is even or odd is an invariant, and it is even both at the start and on a fully covered board, which is why counting area found no obstacle.

Coloring argument

Definition A coloring argument shows that a region cannot be tiled by given pieces. It assigns a color to every square of the grid in such a way that each piece, wherever it is placed and however it is turned, covers exactly one square of each color. The pieces of any tiling then cover equally many squares of every color, so a region whose color counts are unequal has no tiling. Equal counts are a necessary condition only. A region with equal color counts may still have no tiling.

In plain words Choose colors that every piece treats the same way, then compare what the pieces would use with what the region contains.

Example Can $25$ straight pieces, each $1$ by $4$ , tile a 10 by 10 board? The area fits, since $25 \cdot 4 = 100$ . Number the rows and columns from $1$ to $10$ and give the square in row $r$ and column $c$ one of four colors according to the remainder of $r + c$ on division by $4$ . A straight piece covers four squares in a row or column, where $r + c$ takes four consecutive values, so it covers one square of each color. The board has $25$ , $24$ , $25$ and $26$ squares with remainders $0$ , $1$ , $2$ and $3$ , so no tiling exists. The condition is not sufficient. Take a row of four squares and attach one more square above the third and one below the second. These six squares have three of each chessboard color, but the square above the third touches only the third, and the square below the second touches only the second, so both of those dominoes are forced. The first and fourth squares of the row are then left over, and they do not share a side.

Check yourself

Remove the two corners at the ends of row $1$ instead, the squares $(1, 1)$ and $(1, 8)$ . Does the coloring argument still rule out a tiling of the remaining $62$ squares, and is there a tiling?

Show the answer

The square $(1, 1)$ is black, since $1 + 1 = 2$ is even, and $(1, 8)$ is white, since $1 + 8 = 9$ is odd. The board keeps $31$ squares of each color, so the coloring argument no longer gives any obstacle. That alone does not prove a tiling exists, so build one. Row $1$ keeps the six squares in columns $2$ to $7$ , covered by three horizontal dominoes, and each of the rows $2$ to $8$ is covered by four horizontal dominoes. That makes

3 + 7 \cdot 4 = 31

dominoes covering all $62$ squares.

Remove the four squares $(1, 2)$ , $(2, 1)$ , $(7, 7)$ and $(8, 8)$ from the full board. Show that the remaining squares have equal color counts, and decide whether they can be tiled by dominoes.

Show the answer

The squares $(1, 2)$ and $(2, 1)$ are white, with sums $3$ , and $(7, 7)$ and $(8, 8)$ are black, with sums $14$ and $16$ . The board keeps $30$ black and $30$ white squares, so the coloring argument finds nothing wrong. Still there is no tiling. The corner $(1, 1)$ shares a side only with $(1, 2)$ and $(2, 1)$ , and both are gone, so no domino can cover it. Equal color counts are necessary for a domino tiling but not sufficient.

Extend the pattern. Show that if any one black square and any one white square are removed from the full 8 by 8 board, the remaining $62$ squares always have a domino tiling. Use a closed path that visits every square once, stepping each time to a square that shares a side.

Show the answer

One such path starts at $(1, 1)$ and runs along row $1$ to $(1, 8)$ . It steps to $(2, 8)$ and runs back along row $2$ to column $2$ , steps to row $3$ and runs out to column $8$ , and keeps winding through rows $2$ to $8$ between columns $2$ and $8$ . Row $8$ is run from column $8$ back to column $2$ , so the path then steps to $(8, 1)$ and returns through column $1$ to $(2, 1)$ , which shares a side with the start. It visits all $8 + 7 \cdot 7 + 7 = 64$ squares.

Neighboring squares have opposite colors, so the colors alternate along the path, and two squares of opposite colors are an odd number of steps apart along it in either direction. Removing one black and one white square cuts the closed path into two open pieces, one of which is empty when the two squares are next to each other on the path. Each piece contains an even number of squares, because the number of squares strictly between the removed ones is one less than an odd number of steps. Cut each piece into consecutive pairs. The two squares of a pair are neighbors on the path, so they share a side and form a domino, and together these dominoes tile the board. This result is known as Gomory’s theorem.