Take an 8×8 chessboard.
Imagine we have a set of dominoes and we want to cover this chessboard. Each domino covers up exactly two squares. The goal is to cover the chessboard completely, in a way that none of the dominoes overlap or stick off the board.
First question: is that possible?
Answer: It is. Here is one way to do it. Each of the colorful rectangles below represents a domino.
A setup like the one in the picture above, where the board is completely covered with dominoes that don’t overlap and don’t go off the board, is called a tiling.
Now take an 8×8 board and cut off the top right corner and the bottom left corner.
Here comes the puzzle.
Can this board, without the two boxes on the corners, be covered completely with dominoes? Is there a tiling of this board?
There are two possible types of solutions to this puzzle. The format of the solution depends on whether a tiling exists or not.
- There might be a tiling that works. In that case, a solution would be the tiling: a picture of how to cover the board.
- There might be no tiling that works. In other words, it might be impossible to cover this board with dominoes, no matter how many combinations you try. In that case, a solution would consist of a reason why no tiling can work. If there can’t be a tiling, then why not? Can you prove it?
This is called the “Mutilated Chessboard” problem. It doesn’t involve a lot of mathematical sophistication. It does require creative problem solving. My favorite solution to this puzzle is clever, but simple.
Feel free to post thoughts or questions in the comments! I’ll try to respond, and maybe even post hints.
And no full solutions, please. We’ll get to that in the next post.