I was fascinated yesterday to discover a solution to the chessboard prisoner puzzle (Can anyone help me understand this particular solution of the famous two prisoners and a chessboard problem?). My purpose for posting it here is not to ask whether or not it solves the problem (I know it does), it is to ask whether or not the solution is in a sense optimal. Is there an easier way? More efficient?
First we break down our solution into a read operation and a write operation. The read operation determines the location of the key from the board state. The write operation flips one coin and leaves the board in a state that, when read, gives the correct location of the key.
The read operation is performed as follows:
- Counting heads as 0 and tails as 1, find each row sum mod 2, or equivalently note if the sum is even or odd. For practical computational purposes, I'm assuming it's possible for the reading prisoner to mark the odd rows somehow visually.
- Find the sum of the sums in rows {1,2,3,4}. If it's odd, then the key is in one of the rows {1,2,3,4}. If it's even, the key is in one of rows {5,6,7,8}.
- Find the sum of the sums in rows {1,2,5,6}. If it's odd, then the key is in one of the rows {1,2,5,6}. If it's even, then the key is in one of rows {3,4,7,8}.
- Find the sum of the sums in rows {1,3,5,7}. If it's odd, then the key is in one of the rows {1,3,5,7}. If it's even, then the key is in one of the rows {2,4,6,8}
The reader now has the row location of the key. For each possible combination of the sums found so far being even or odd, there is a unique row matching all three criteria. This follows from the fact that any three way intersection between either {1,2,3,4} or its complement, {1,2,5,6} or its complement, and {1,3,5,7} or its complement has exactly one element. Another way of thinking about it is that each sum check rules out half of the remaining possible rows, so after 3 sum checks you have narrowed it down to one and only one possible row.
- Repeat the same process for the column sums and the same sums of these sums. The reader now has the column location of the key
Now for the write operation! The writing prisoner does the following:
- Compute the row sums and the same sums of row sums described for the reader
- If the sum for rows {1,2,3,4} is wrong, i.e. the key is in fact in one of these rows but the sum is even when it should be odd, then one of the coins in one of the rows {1,2,3,4} must be flipped to correct this. If the sum is correct, then coins in those rows must not be flipped.
- Similarly, if the sum for rows {1,2,5,6} is wrong, then one of the coins in one of those rows must be flipped to correct this. If the sum is correct, then none of the coins in those rows must be flipped
- Finally the writer checks the sum for rows {1,3,5,7}. If it's wrong, then one of the coins in that row must be flipped to correct it. If it's correct already, then none of the coins in those rows can be flipped.
The writer now knows the row location of the coin they must flip in order for the row location to be correctly encoded on the board. Again, this can always be done with the flip of one coin in the appropriate row, no matter what combination of sums were correct or incorrect to start with. Flipping a coin in the first row, for example, changes all three sums (which you would do if they all started out incorrect). Flipping a coin in the 8th row changes none of the sums (which you would do if they all started out correct).
The key observation is that, for every board state, there is a choice of row that, by flipping any coin in that row, the board now encodes the row location of the key for the reader correctly.
The writer now goes through exactly the same procedure in the columns. As in the rows, there always exists a choice of columns such that flipping just one coin in that columns changes the board state into one that encodes the column location of the key for the reader correctly.
The writer then flips the coin in the exact row and column identified and confidently walks out, knowing that the reader will correctly locate the key by finding and interpreting the row and column sums from the new board arrangement.
What led me to this solution was first to realize that the reader must perform the task of computing some specific agreed-upon projection of the space of all possible board states into the 64 squares. The writer then must be able to find a 'neighboring' board state (one that only differs from the initial board state by the flip of one coin) whose projection gives the correct square for any initial board state. Row and column sums came to me as natural forms of projections, and the rest of the solution fell out from there.
So my question is, can we do better?? I think my solution has a lot going for it. It is easy enough to memorize the procedures needed (I tried it out and was able to do it successfully on a real chessboard with real coins). It is possible to perform all of the calculations mentally, and there are a reasonable number of computations needed so that the procedure can be done accurately in a reasonable amount of time. It turns out it is much easier to perform the task mentally if all of the heads coins are simply removed from the board, and actually relatively difficult if you can't use markers to mark the end of each row with its sum parity because of human brain memory issues.
But anyways, the actual question: is there a more practical form of projection, computationally? Is there any way to know if a particular encoding/decoding scheme is optimal? What does it even mean for a solution to be optimal for this problem?
Not sure whether this meets your criteria, but here's a simple-to-describe solution:
Think of the squares as numbered from $0$ to $63$, and notice that (because $64=2^6$) the binary representations of these labels constitute all $6$-bit binary strings.
The first prisoner will encode the secret label as the bitwise XOR of the labels of all the heads-up coins. To do so, he computes the initial message (the XOR of all the initially heads-up coins), compares it with the desired message (the label of the square where the key is hidden), and flips the coin whose label is the XOR of the two (i.e. the binary string with a $1$ in exactly the positions where the two strings differ). This flips the desired bits of the message.