No: a chessboard with two opposite corners removed cannot be covered by 31 dominoes, even though there are exactly enough of them, since 62 squares = 31 × 2. The two removed corners are the same color, so the board is left with 30 squares of one color and 32 of the other. Every domino covers two edge-adjacent squares, and neighboring squares always have different colors, so each domino covers one of each color. Thirty-one dominoes would need 31 of each. The area matches; the color counts don’t. That is the whole mutilated chessboard problem, solved without placing a single domino.
The puzzle
Start with an ordinary 8-by-8 board: 64 squares, 32 of each color. Remove the top-left and bottom-right corners. What is left has 62 squares, and you have 31 dominoes, each the size of two squares. Can you lay them flat, edge to edge, so that every square is covered exactly once?
The natural first move is to start placing dominoes. Rows go in easily, but the last few squares never line up. The trouble is that failed attempts prove nothing; perhaps the next arrangement works. To show it is impossible, you need a reason that covers every arrangement at once.
Why the mutilated chessboard can’t be covered
The reason is color.
- Opposite corners lie on the same long diagonal, and a diagonal step changes the row and the column by one each, which never changes the color. So the two removed corners share a color.
- Before the cut there were 32 squares of each color. Now there are 30 of one color and 32 of the other.
- A domino always covers two squares that share an edge, and those always have different colors. Every domino, wherever it goes, covers exactly one square of each color. The video slides a domino across the board to show this.
- So 31 dominoes would cover 31 squares of each color. The board has only 30 of one of them.
In fact at most 30 dominoes can ever fit, and at least two squares of the more common color are always left bare.
A logic textbook puzzle that traveled
The philosopher Max Black posed the puzzle in his 1946 textbook Critical Thinking, with a hint at the coloring solution. His interest was creative insight: the moment a problem that resists brute effort suddenly looks easy.
From there it spread through recreational mathematics. Solomon W. Golomb, who had invented the word polyomino in 1953, discussed it in his 1954 article “Checker boards and polyominoes” in The American Mathematical Monthly. Martin Gardner ran it in his “Mathematical Games” column in Scientific American in February 1957 and gave the answer in March. George Gamow and Marvin Stern included it in their 1958 book Puzzle-Math.
Gomory’s theorem: remove one of each color
Change the cut and the answer flips. Removing any two squares of the same color is always impossible, by the same counting. But Gomory’s theorem, named for Ralph E. Gomory, says that if you remove one white and one black square, wherever they are, the remaining board can always be covered exactly with 31 dominoes.
The proof is a closed path. Draw a single loop that visits all 64 squares, stepping between neighbors and returning to its start. Along the loop the colors alternate. Cut out one black and one white square and the loop breaks into two pieces, and because the colors alternate, each piece contains an even number of squares. Lay dominoes along each piece, two squares at a time, and the board is covered. The proof appeared in print in Ross Honsberger’s Mathematical Gems in 1973.
Domino tilings are not only a game. In statistical mechanics they are called dimer models, an idea that goes back to work by Ralph H. Fowler and George Stanley Rushbrooke in 1937. For another puzzle where counting the right thing beats trying every case, see four letters in four envelopes.
Enough dominoes. Impossible board.
