One of my favorite YouTube channels, 3Blue1Brown, recently uploaded a video about a fascinating chessboard puzzle, with another fantastic channel, standupmaths. I loved the videos, but I found that the explanation was scattered throughout the video and may have been difficult to grasp for some viewers. Here I’ll go through the process of developing a solution that summarizes and condenses what was shown in the video.
I’ve made an interactive demonstration of this puzzle here. You can try to follow along with it open, but I haven’t written this for that.
You are locked in a room with a chessboard. Each square is covered with a coin, and underneath one coin is a key. You know what coin the key is under. You have to flip over one coin on the chessboard, and then leave. Your friend comes in and must figure out what coin the key is under. There’s no clever trick or metagame here, it’s just math.
Making it more technical
When I’m presented with a puzzle like this, I have some issues with keeping track of everything if I don’t unpack it and get it into more mathematical terms. First, we know that binary will be involved, since the coins have two states (heads and tails).
What’s the overall goal of the game? We need to be able to communicate the position of the key to the friend. That simplifies to needing to communicate a number between 0 and 63 (zero-indexed because this is computer science). We’re given a set of 64 0s and 1s. We need to develop a system to arrange and count those 0s and 1s, so that they output a number between 0 and 63. The real challenge is this: We need to be able to, given a desired output, flip one of the bits so our system gives that output.
The big idea
Parity. That’s just whether a number is even or odd. The big idea is that if you add, or subtract, 1 from a number, it will always change from even to odd.
The first logical thing is to assign a number to each square on the board. We’ll just go left to right, row by row. It doesn’t totally matter how you do it when the full solution is understood, but an easier counting system is better especially if you’re concerned about running into this situation in real life.
Binary Numbered Board
This next paragraph won’t use these yet, but keep them in your head.
We know that since we want the board to encode a state when we’re finished, the board must encode some sort of state before we’ve done anything. It doesn’t matter what that state is for now, we just want to have some starting number. Let’s say that’s
110100. We’ve also found what number we want to encode with the board. Let’s say that number is
100011. The key here is to look at this in the context of parity. We don’t need to encode all of
100011, just what bits need to be flipped to get it. That can be done with the XOR logical operation, which simply says whether the bits are the same or different. Doing that gives us
Now all we have to do is encode that value of
010111 into the chessboard. Here’s the clever part: We can just flip that numbered coin. That may not make sense now, but this next part will make that make sense.
Let’s suppose that all we care about is making just the last (least significant) bit correct. In that case, we have 32 coins that we could flip over. Those 32 coins are all the ones that end in 1, because we have established that the number we want to encode is
010111, which has an LSB of 1. We can flip any of those coins. The parity of all of those coins that have a last bit of 1, will be the last bit of our final value.
Summarized into one sentence: The simple act of numbering these coins gives each one a unique combination of bits to flip: its own value.
And this applies to all of the bits. The second to last bit of the number we want to encode will be encoded in the parity of all the numbers with a second to last bit of 1. The important thing here is that this also divides the possible numbers we can choose from 32 down to 16. We’ve gone from
****11, (in reference to
While it’s easy to go without visualizations to choose what coin to flip, it’s a good idea to look at the puzzle visually when trying to decode it. First, let’s look at the coins that, when flipped, will flip the last bit. Reiterating: These coins flip the last bit of the value represented by the board, because their last bit is 1.
How about the ones where the second to last bit is 1?
Here’s the clever part. When we know we want both of the last 2 bits to be flipped, we are now down to 16 possible coins: the 4th and 8th column in this example.
When 3rd to last bit is 1:
When doing the first 3 bits, all that happens is that the board is rotated 90 degrees. Here’s the 3rd bit:
And finally, the first bit is encoded in the parity of these:
A full example
Highlighted in red is the coin with the key under it.
That coin is position 51:
110011 in binary.
The value currently represented by the board is
101110. The parity of all the coins in positions with the last bit of 1, is 0. The parity of all the coins in positions with the second to last bit of 1, is 1, etc.
Doing XOR on these two numbers gives us
011101. Now, what coin do we flip? The coin in position
The person decoding it now just has to calculate the new value of the board. Since we’ve flipped the bits that we want to flip, the value of the board is now
110011. We’re free.