Chessboard Coin Problem
How to encode a chessboard tile by flipping a coin?
Problem
Suppose you and your friend have been taken hostage. Your kidnapper gives you a chessboard and then lays a coin on each tile of it, either showing heads or tails, completely randomly. Then he chooses one tile at random, the position of which you have to communicate to your friend. You have to flip one coin, after which the chessboard is shown to your friend who has to determine the chosen tile based only on the resulting layout. Your friend and you are allowed to devise a strategy beforehand, but there is no way to cheat, the only way you can transfer information is through the flipping of that one coin.
Solution
(You should probably know a little bit about binary numbers and logical operators to properly understand the following solution. I won’t go super deep into the details as the post is already really long as is.)
Now this might look like an impossible task at first, after all your friend can’t even determine which coin you flipped, the initial state could have been anything and there are 64 possible solutions. However, there is a strategy that guarantees you to win every time.
In fact, this particular strategy works for arbitrarily big boards, as long as the number of tiles is a power of two (1, 2, 4, 8, …, 64, …).
Let’s first consider simpler versions of the problem:
1 tile is obviously very easy: you flip the one tile and then your friend chooses it as the solution.
2 tiles is trickier, but still fairly simple. You agree on one tile (for example the first) that will determine the position. Then you agree on one coin side that signals the first tile as the solution, the other signals the second. When you are given the coins and the position and they don’t match you just flip the signaling (first) coin, if they match you flip the non-signaling coin.
However, this strategy won’t work for more tiles than that.
—
At this point it is helpful to change how we think about the problem. We can assign numbers to the chessboard tiles (an index) from 0 to n — 1 (where n is 64 in the case of the chessboard, we start from zero because it will be more convenient later). It should be noted that we can represent these numbers (the index) in binary with exactly log2(n) bits (6 in the case of the chessboard).
Moreover, we can represent the state of a coin (heads or tails) as a single bit (0 or 1). This allows us to properly use logical operators on them.
One that is of particular interest is the XOR operator. You can think of it as returning 0 if the two inputs are the same and 1 if the two inputs are different. Another useful way of thinking about it is, that XORing a bit with 1 flips it, while XORing it with 0 just leaves it as is. This yields a further powerful property: when XORing a bunch of bits, flipping any of the input bits is guaranteed to flip the output bit. We can use this fact to solve the riddle.
—
So let’s consider 4 tiles: we can represent the index of any tile with 2 bits. However, we can only flip one tile, so we can’t just take any two tiles at face value. We need to determine the index in another way. To obtain the first bit of the index of the encoded position we XOR the first and third tile, to obtain the second bit we XOR the first and second tile.
Now when we get the chessboard and position, we calculate the index encoded by the initial state. If the position we need to encode matches the initial index we got we flip the last bit, as that doesn’t affect the output. If we want to change the first bit of the encoded number, we flip the third tile, if we want to change the second bit, we flip the second tile and if we want to change both bits, we flip the first tile.
So XORing enables us to flip all combinations of the output bits no matter what we got as the initial state, or which position we must communicate to our friend.
Moreover, this strategy generalizes nicely to more tiles. For 8 tiles we extract 3 bits representing the index, XORing 4 tiles at a time, for 16 tiles we extract 4 bits from 8 tiles at a time, and so on. The illustrations below should help.
To get the nth bit of the index, you XOR the colored tiles in the corresponding row. Then you convert the output bits to decimal to get the index of the encoded tile.
Programming
If you are not interested in programming, you can safely skip this part.
What I really like about the approach above is how easy it is to implement it.
Decoding
You decode the chessboard by extracting the index bits from it. For every index bit you apply a mask to the chessboard, XOR every coin, and write the result to the bit. You obtain the mask by using powers of two to generate alternating patterns between 0 and 1 (the colored tiles). Then you convert the output bits into decimal, the result is the index of the encoded tile.
Encoding
First you decode the initial state of the chessboard with the method described above. Then you bit-wise XOR the initial encoded position and the one you want to encode to determine which bits are different. Now the mind-blowing part is that the result of the bit-wise XOR is actually also the index of the tile you have to flip to encode the correct position, measured backwards from the last tile of the board. This has to do with how we generated the mask when decoding, the mask (the colored tiles in the illustrations above) are basically binary numbers when read vertically, ascending from right to left.
Source Code
You can look at the source code on GitHub, I tried to keep it as clean and simple as possible.