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.