Tag Archives: chessboard

A Rook Game

Posted on by

Problem: Two players take turns moving a rook on an 8×8 chessboard. The rook is only allowed to move south or west (but not both in a single turn), and may move any number of squares in the chosen direction on a turn. The loser is the player who first cannot move the rook. What is the optimal play for any starting position?

rook-board

Solution: Take advantage of the symmetry of the board. If the rook is not on the diagonal, the optimal strategy is to move it to the diagonal. Then when the other player moves it off, your next move is to move it back to the diagonal. If your opponent starts their turn with the rook always on the diagonal, then you will never lose, and by the symmetry of the board you can always move the rook back to the diagonal. This provides an optimal algorithm for either player. In particular, if the rook starts on a square that is not on the diagonal, then player 1 can guarantee a win, and otherwise player 2 can.

Symmetry is one of the most powerful tools in all of mathematics, and this is a simple albeit illustrative example of its usage.

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.