Tag Archives: dominoes

Tiling a Chessboard with Dominoes (Opposite Colors Removed)

Posted on by

This is a natural follow-up to our first gallery entry on the impossibility of tiling certain chessboards with dominoes.

Problem: Suppose we remove two squares from a chessboard which have opposite color. Is it possible to tile the remaining squares with 2-by-1 dominoes?

Solution:

From Honsberger's Mathematical Gems I.

Notice that if we remove two squares of opposite color, then there is only one way to place dominoes on the remaining squares according to this scheme (one cannot tile a domino across the “walls”). Removing two squares of opposite color ensures there is an even number of squares between the removed squares, and so the dominoes will fit as desired. In other words, the two “paths” from A to B, starting on any side of A, contain an even number of squares, and so placing a domino every two squares will fill the path with a good tiling.

Not only does this method provide a positive answer to the solution, it gives a constructive answer. If we had some odd desire to do so, we could write an algorithm which tiles any chessboard where two squares are removed, (moreover, it would run in linear time). It’s not obvious at first whether such an algorithm exists, as the average human attempt to tile a board with two random squares removed would likely require some backtracking. In other words, human solutions would generally be heuristic in nature, but this analysis gives a solution that any person could utilize.

Tiling a Chessboard

Posted on by

Problem: Take a chessboard and cut off two opposite corners. Is it possible to completely tile the remaining board with 2-by-1 dominoes?

Is it possible to tile this board with 2-by-1 dominoes?

Solution: Notice that every domino covers exactly one white tile and one black tile. Counting up the colors, we have 32 white and 30 black. Hence, any tiling by 2-by-1 dominoes will leave two extra white squares unaccounted for. So no such tiling is possible.

Problem: Cut one corner off a chessboard. Is it possible to tile the remaining board with 3-by-1 dominoes?

Solution: Analyzing this problem with the normal chessboard admits no nice proof like before. Specifically, any tile covers either two white and one black tile, or two black tiles and one white tile, so a counting argument is much more difficult.

In a moment of divine inspiration, we realize that the standard coloring of the chessboard is arbitrary. We decide to repaint our board as follows:

Our new coloring makes the proof trivial.

Clearly, any 3-by-1 domino covers exactly one black square. Counting up the colors once more, we see that there are 22 black squares. Since there are 63 squares in all, we must have 21 3-by-1 dominoes, each covering one black square. This leaves one black square unaccounted for, and so no such tiling is possible.

Notice that if we omit the word “chessboard” and just give a colorless grid, this “divine inspiration” would certainly be much more miraculous.

Furthermore, this gives a nice method of proof for any $ n$-by-1 dominoes on an $ m \times m$ board, where $ n < m$, and we cut off a certain number of squares. Just look for a useful coloring, such that each domino covers a helpful number of squares of a certain color.