Tiling a Chessboard with Dominoes (Opposite Colors Removed)

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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s