A regular chessboard is an 8×8 grid (having 64 squares). If you are given 32 dominos where each domino can cover two squares on the chessboard, you can cover all the squares of the chessboard.
Someone mutilated the chessboard and removed the upper left and lower right corners. The mutilated board has 62 squares. You are given 31 dominos. Can you tile the mutilated chessboard with the 31 dominos?
Let students try to find a way to tile the mutilated board. After a while some of them will claim that it can’t be done. The algorithms we have sketched so far describe how something can be done. If the board can indeed not be tiled, how do we proceed?
One could write a program that systematically generates all possible ways to tile the mutilated board. The number of ways the mutilated chess board can be tiled is finite, but it is a large number. If the program fails to find a possible tiling, we can conclude none exists.
However, we can show that no tiling exists by a direct proof. This means that a program checking all possible tilings would not find one.
Here is the argument:
A tile placed on the chessboard will always cover one white square and one black square. Therefore, a collection of tiles placed on the board will cover equal numbers squares of each color. The mutilated board has two white squares removed and it thus has 30 white squares and 32 black squares. If every tile covers one black and one white square and we have more white squares, we can conclude that the mutilated board cannot be tiled. If the two black corners are removed instead, then 32 white squares and 30 black squares remain, so it is again impossible.
We can tile a mutilated board only if one white and one black corner are removed (but the problem said corners on opposite sides of a diagonal were removed). Wikipedia has a nice description of this problem – http://en.wikipedia.org/wiki/Mutilated_chessboard_problem.
Another chessboard tiling puzzle
Remove from the regular 8 by 8 chessboard one square (you choose the square). You are given 21 tiles where each tile is L-shaped and is made up by 3 squares. Can we cover the mutilated chessboard so that all squares except the deleted one are covered and no L-shaped tiles overlap?
No matter where the deleted square is on the board, we can always tile using the 21 l-shaped tiles. A recursive argument provides a simple way to prove this.
Hard to find, but easy to check?
For many puzzles, finding the solution is hard, but once you are given a solution, it is easy to check that it is indeed one. Convincing someone that no solution exists is generally also hard. The characteristics of puzzles and other problems of “easy to check but hard to find” play a crucial role in algorithm design and analysis.
