Wednesday, 26 January, 2022
HomeOpinionChessboard Challenge is this week’s top puzzle for the lockdown

Chessboard Challenge is this week’s top puzzle for the lockdown

The pure joy of brainteasers sometimes requires a bit more than trial and error.

Text Size:

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 2×1 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.


Also read: Tiger King on Netflix is outrageous, but more weird is Indians following it


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 2×1 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. –Bloomberg


Also read: Dear Insta influencers, Covid-19 charity is not an excuse to promote your products


 

Subscribe to our channels on YouTube & Telegram

Why news media is in crisis & How you can fix it

India needs free, fair, non-hyphenated and questioning journalism even more as it faces multiple crises.

But the news media is in a crisis of its own. There have been brutal layoffs and pay-cuts. The best of journalism is shrinking, yielding to crude prime-time spectacle.

ThePrint has the finest young reporters, columnists and editors working for it. Sustaining journalism of this quality needs smart and thinking people like you to pay for it. Whether you live in India or overseas, you can do it here.

Support Our Journalism

Most Popular

×