There is a checkerboard whose upper left and lower right squares have been removed (Figure 5.1). There is a box of dominoes that are one square by two squares in size.
Question: Can you exactly cover the checkerboard with the dominoes?
Potential Application: For a practical application of this problem, consider a real estate developer who owns land and intends to sell it in lots. Including two portions owned by the school district, the shape of the land happens to be a perfect square. Unfortunately, from the developer's viewpoint, the school district refuses to sell its land. The two missing pieces are, respectively, the upper left and lower right squares. So the developer has decided that each lot will also be a square. A market survey has uncovered a potential obstacle to the plan of selling all of the land the developer owns. The buyers are not interested in single lots, but instead each wishes to purchase land in the shape of a rectangle consisting of two adjoining lots. Can the developer arrange the lots to permit all of them to be sold?
Difficulty: This puzzle was suggested in the middle 1960s by John McCarthy. The notion was that a computer program would be hard pressed to solve it. In particular, it was felt that a computer program would be very unlikely to find the solution that a clever person might.
Human Solution:
An inventive person might give the following solution. Indeed, this is the solution that McCarthy was challenging a computer to find.
A detailed discussion of this puzzle and others is given in Automated Reasoning: Introduction and Applications, by Larry Wos, Ross Overbeek, Ewing Lusk, and Jim Boyle. The book, published by McGraw-Hill, includes a diskette of the automated reasoning program OTTER, which can be used to solve puzzles as well as extremely challenging problems in mathematics and logic.
Those who have OTTER already may simply take the input and start experimenting.