A jailer takes two prisoners and tells them "we're going to play a game. If you win, both of you will be set free. I will take prisoner #1 into a room. The room will contain an empty chessboard. I will point to one of the squares on the chessboard. This is the 'magic square'. I will then take 64 coins, and put a coin on each square of the chessboard. I will choose which coins are heads-side up and which are tails-side up. Prisoner #1 must then choose exactly one coin on the board and toggle it. I will then take prisoner #1 out of the room, and bring prisoner #2 into the room. Prisoner #2 will look at the chessboard, and must find the 'magic square'. There is only one guess. Sounds good? Before we start, you are allowed to talk to each other and plan out a strategy, but I will stand here and listen to you. Once the game starts, you will not be able to communicate with each other." What's the strategy?
Enumerate all 64 squares on the board, 0..63. We will work with these values in binary, as 6-bit unsigned integers: 000000, 000001, 000010, etc.
For example:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 |
| 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 |
| 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 |
| 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 |
| 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 |
| 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 |
Or, in binary:
| 000000 | 000001 | 000010 | 000011 | 000100 | 000101 | 000110 | 000111 |
| 001000 | 001001 | 001010 | 001011 | 001100 | 001101 | 001110 | 001111 |
| 010000 | 010001 | 010010 | 010011 | 010100 | 010101 | 010110 | 010111 |
| 011000 | 011001 | 011010 | 011011 | 011100 | 011101 | 011110 | 011111 |
| 100000 | 100001 | 100010 | 100011 | 100100 | 100101 | 100110 | 100111 |
| 101000 | 101001 | 101010 | 101011 | 101100 | 101101 | 101110 | 101111 |
| 110000 | 110001 | 110010 | 110011 | 110100 | 110101 | 110110 | 110111 |
| 111000 | 111001 | 111010 | 111011 | 111100 | 111101 | 111110 | 111111 |
enum CoinState {
Heads,
Tails
};
// uint6 is a 6-bit unsigned integer, from 0 to 63
CoinState GetCoinState(uint6 square_index);
uint6 ComputeXOROfHeads() {
uint6 xor_of_heads = 0;
for (uint6 i = 0; i < 64; i++) {
if (GetCoinState(i) == Heads) {
xor_of_heads = xor_of_heads ^ i; // This is a bitwise XOR
}
}
return xor_of_heads;
}
void ToggleCoin(uint6 square_index);
uint6 GetMagicSquareIndex();
ToggleCoin(GetMagicSquareIndex() ^ ComputeXOROfHeads());void GuessMagicSquare(uint6 square_index);
GuessMagicSquare(ComputeXOROfHeads());- The number of squares on the board must be a power of 2. Otherwise, there is no solution. I will explore this in more detail below, using group theory. There is an alternate explanation of this constraint based on graph-coloring [YouTube video].
- There are ways to optimize the above algorithm to make it more human-friendly to compute [YouTube video].
Prisoner #1 sees board state 
. Then, prisoner #1 computes 
and toggles that coin to make the board state 
which is equal to 
.
Feynman's Algorithm:
- Write down the problem.
- Think very hard.
- Write down the solution.
I find it insufficient to merely describe the solution, I am motivated to describe the methodology used to arrive at it. The point of algebra (both in its elementary form and its various more abstract forms) is to provide a means to express the constraints of a problem such that the solution flows natrually from the constraints. Instead of anticipating a logical leap to an answer, you should continue to refine the expression of constraints until the answer has no choice but to reveal itself to you.
We are interested in understanding 2 sets:
, the set of all possible chessboard states. Note 
, the set of all squares. Note 
We would like to define a function that the prisoners can use to encode a square with the chessboard state:
- Our objective is to convey a secret
. - Given some initial chessboard state
chosen by the jailer - Prisoner #1 will want to change the chessboard state from
to 
by toggling a single coin such that 
- Prisoner #2 will observe the chessboard state
and compute 
, using that to guess 
Since we want to understand how the function 
behaves with respect to changes in its input, we will need more algebraic structure. We need to make 
and 
groups, and make a group homomorphism.
I have included a review of group theory in the appendix.
In order to make a group, we need to be able to answer the question what does it mean to add two chessboard states together? We can answer this by reinterpreting to be a set of chessboard state deltas. Note, this is a formality. There is essentially no difference between a group of states and a group of state deltas, except the latter motivates the intuition of what it means to add two group elements together.
We will choose to make the vector space 
, alternately represented as the set of all 64-bit bitvectors under the XOR operator. To review, in the field 
, the following identities are true:
The meaning of 
vs 
depends on whether we are interpreting the group as chessboard states or chessboard state deltas:
| Interpretation of |
Meaning of |
Meaning of |
|---|---|---|
| Chessboard states | Tails | Heads |
| Chessboard state deltas | Do not toggle the coin | Toggle the coin |
-
Note the standard basis
, consisting of vectors such as 
, is the set of valid moves that prisoner #1 can make, since each standard basis element is a delta that toggles exactly one coin. -
The identity element of
, known as 
, is the 0 vector: 
-
The inverse of every element in the group is itself,
. Or, x XOR x is always 0. The intuition captured here is that toggling the same coin twice results in an unchanged board. -
happens to be Abelian. In other words, addition is commutative, or
-
Let
be the move that prisoner #1 will make. Therefore, 
-
Let
be a group homomorphism from 
. In particular, we want to guarantee that is surjective, aka "onto", aka 
. Otherwise, we would not be able to encode all possible magic squares. -
We know that
is a set with 64 elements, but we have not yet decided how to make it into a group. That will come later.
Let's now solve for 
, the move prisoner #1 should make:
We will now introduce the usage of the inverse image, 
Therefore:
The set on the right-hand side contains all deltas that can be applied to to make 
. We need to guarantee that this set contains at least one legal move.
To do this, we must guarantee that each element 
must have at least one standard basis element 
such that 
. In other words 
. This is straightforward. There are 64 elements in 
(there are 64 possible valid moves prisoner #1 can make) and there are 64 elements in (there are 64 squares on the chessboard). This is made even easier by the fact that every standard basis element toggles exactly one coin, so it has already "picked a square". We can then construct a straightforward one-to-one mapping between the two sets and .
There are two main questions that remain:
- We have defined the values of
where 
. We must now define the remaining values of 
where 
. - We still need to make into a group. Without this, we cannot compute
, for we have not defined the 
operator yet.
And the answers:
- Each element can be expressed as a sum of basis elements,
for the basis elements corresponding to the squares with a heads-up coin. The intuition captured here is that every chessboard state can be arrived at by starting with an all-tails board and proceeding with a series of valid moves (aka single coin toggles) 
And we already have definitions of
for all , so we are done here. - Now comes the interesting part. What do use as a group for ?
Much of what we've discussed above is mere formalism. Now we get to the core of the problem: choosing a group for .
The first intuition many seem to have when trying to solve this problem is to make the additive group of integers mod 64, also known as 
. This is often chosen because it is a simple, well-known group. It seems promising at first, but you quickly run into problems when you discover that for almost all chessboard states 
, not every square is reachable with a single coin toggle. This approach of just picking your favorite group does not work; the choice of group is constrained by the homomorphism .
The main clue is that every element in is its own inverse: 
. When we apply , we realize that must also be self-inverting:
Since 
:
is not self-inverting. For example, this would require that 
, but in that group 
. Therefore, we cannot construct a homomorphism such that 
. It is impossible.
Which group has 64 elements and is self-inverting? The vector space 
, or the set of 6-bit bitvectors under XOR. It turns out, must be the "same kind of group" as , also a vector space over . We go into more detail about this below.
You may not yet be convinced that is a homomorphism. We can represent as 
where 
is a constant 
matrix, 
is a 
vector, and 
is a 
vector. looks like this:
Matrix multiplication is a form of group homomorphism.
Recall:
We can make this minor simplification:
We will now translate the math above into the C++ code in the first section.
- Wherever we see , we replace it with
^, the bitwise XOR operator. - Wherever we see
where 
is the current board state, we replace it with ComputeXOROfHeads(). - Wherever we see
, we replace it with a uint6representing the 6-bit encoding of the square on the chessboard. - The implementation of
ComputeXOROfHeadscorresponds to
GetMagicSquareIndex() ^ ComputeXOROfHeads()corresponds to
- Imagine a 9x9 board. There will be 81 squares on it. We need 7 bits to represent the square indices, 0 to 80 inclusive. However, the full range representable by 7 bits is 0 to 127 inclusive. This means some board states encode values of 81 to 127, which do not correspond to any magic square. Prisoner #1 will have 81 options out of a space of 128, and it is not guaranteed that the option prisoner #1 needs will be present in the set.
- Another explanation [YouTube video] looks at the problem from the standpoint of graph coloring. Imagine a graph arranged like an
-dimensional hypercube, where is the number of squares on the chessboard. There are colors. We need to assign each node a color such that all colors are reachable from one of its direct neighbors. The number of nodes will always be a power of 2 (due to the number of possible chessboard states being 
). If the number of colors is not also a power of 2, it will not divide evenly. Some colors will be represented more than others. The video has a more detailed explanation.
Remember above we said that, in order to guarantee the existence of a legal move in 
, we must guarantee . This was assuming . What happens if the latter is not true?
- Let's say that
. We cannot even state at this point that is a group. It might only be a set. - We can still have a one-to-one mapping between
and (there is still the same number of legal moves as there are possible magic squares). But then 
- The jailer has control over and , which implies the jailer has control over . The jailer could then choose values such that
. And then prisoner #1 would have no legal move that could be made to put the board into state such that .
So can we guarantee that ?
The answer is yes, if and only if 
is a power of 2. Because of the fundamental homomorphism theorem:
Fundamental Homomorphism Theorem:
Let
and
be groups, and let
be a homomorphism.
- The kernel of
- The image of
- The image of
Now we are getting into more advanced territory. Without explaining all the derivations, we are going to quickly compose a bunch of theorems to prove that the order of the image of any homomorphism from is a power of 2. If you are interested, please do some independent research! The details behind these theorems are fairly accessible!
- We need to know the definition of "normal subgroup". But every subgroup of an Abelian group is normal, and is Abelian, so we can nip that complexity in the bud.
- LaGrange's theorem states that for any finite group , the order of every subgroup of evenly divides the order of . Since the order of here is
, then every subgroup (and hence every possible kernel) has order 
where 
.
At this point, if we know how many elements are in the quotient group 
, then we know how many elements are in the image of . And yes, it is as simple as 
, which is 
where 
.
Note that the fact that the image of is isomorphic to the quotient group elaborates on the claim above that must be the "same kind of group" as . In fact, all homomorphism images of 
are isomorphic to 
. In other words, they are all vector spaces over the same field.
- A group is the tuple
. - It is a set with an associative binary operator
- The set contains an identity element
such that 
- Each element
has an inverse element 
such that 
- The operator may or may not be commutative (when it is commutative, we call the group "Abelian")
- A vector space
is a group consisting of vectors with -dimensions over the field 
. - Every vector space has a basis: a set of elements
such that each element of the vector space can be expressed as a unique sum of basis elements: 
where 
- A standard basis is a basis of a vector space where each basis element is a vector of the form or
, etc - A group homomorphism is a function
from group to group such that 
- As corollaries to the above, for any group homomorphism , the following are true:
and 
- The image of a set under is
- The preimage or inverse image of a set under is
