Kominers’s Conundrums: The Corner-Cutting Chessboard

(Bloomberg Opinion) -- Last week, we solved a puzzle of light switches – all it took was a short trip to a different part of our brains. This week, we’ll be interrogating another common household object: the chessboard.

My Bloomberg Opinion colleague Noah Smith recently reminded me of the following problem first posed by Max Black, a British-American philosopher:

Suppose we take a standard 8×8 chessboard and remove two squares from opposite corners, as shown in the picture below. Is it possible to place non-overlapping 2x1 dominoes on the board so as to exactly cover all the remaining squares? (No letting any of the dominoes hang off the board’s edges!)

One of the nice things about this problem is you can experiment with it directly. Why not grab a board and try placing some dominoes – or 2×1 slips of paper -- yourself?

Beginning to fill out the board isn’t much of a problem. The first dominoes can go almost anywhere. Before too long, though, it’s easy to get blocked into a corner.

If a bit of trial and error doesn't lead to a breakthrough, you’ve arrived at one of the first major tests in becoming a puzzle ninja (and for too many people, the last). It’s easy to get frustrated and, well, give up.

Here’s a better idea: Take a step back and start reasoning about the problem with logic.

Start by reflecting on those trials and errors: No matter how densely the dominoes are packed, there’s a hole or empty corner. If there were a lot of possible coverings, the solution would probably have emerged pretty quickly. And even if there were only a few, enough searching would find one. Running into the same error in numerous trials reinforces a terrible feeling: Perhaps … there’s no way to do it!

But would the puzzle’s author actually set a task that can’t be completed? That definitely can happen – but it doesn’t mean the puzzle has no solution; rather, the “solution” is a logical argument conclusively proving that no covering exists.

So now let’s start thinking about the structure of the problem itself. Can we somehow make ourselves completely certain that there is no way to cover the modified board?

Yes, we can! The key observation is so simple it hides in plain sight. Since colors on a chessboard alternate, no matter how you place a domino, it always covers one square that’s black, and one that’s white. Why is that important? It means that no matter how many (non-overlapping) dominoes we place on the board, they cover the same number of black and white squares. If we place seven dominoes, then we cover seven black squares and seven white squares. If we place 17, then we cover 17 of each.

A normal chessboard has 64 squares, so our modified chessboard has 62. To cover 62 squares with 2x1 dominoes, we would need 31 of them – and since every domino covers one square of each color, we’d end up with 31 black squares covered and 31 white.

That sounds fine – until we count up the squares at our disposal. Both of the deleted corners are black, so the modified board has 32 white squares, and just 30 black ones. There’s no way to cover all the squares with dominoes while making sure that we cover the same number of each color. And that means no perfect covering can exist.

Voila – problem solved! And along the way we learned some of the value of logic over endless trial and error: Solving this puzzle was beyond reach without it. (And if you are still craving a perfectly covered board, just cut two corners off the same side of the board instead.)

Is it always possible to tell when a covering like this is possible or not? Unfortunately, probably not. A 2005 thesis (hat tip: Noam Elkies) suggests that it can sometimes be quite difficult to figure out whether a given modified chessboard has a domino covering -- at least if the number of black and white squares on the board is the same.

But now that we’ve solved our board, at least, why not try out this puzzle, which relies on similar sorts of reasoning. Or alternatively, this could be a great time for a domino rally.

Although as several astute readers pointed out, the solution implicitly assumes an incandescent light bulb, since it relies on the bulb generating heat. If you’ve already made the switch to LED, try these solutions from physics Nobel laureate Richard Feynman (hat tip: Tom Ledbetter and Samuel Lipoff.)

This column does not necessarily reflect the opinion of Bloomberg LP and its owners.

Scott Duke Kominers is the MBA Class of 1960 Associate Professor of Business Administration at Harvard Business School, and a faculty affiliate of the Harvard Department of Economics. Previously, he was a junior fellow at the Harvard Society of Fellows and the inaugural research scholar at the Becker Friedman Institute for Research in Economics at the University of Chicago.

©2020 Bloomberg L.P.