A few weeks ago I wrote about the Devil's Chessboard problem. In it, I described a solution to the puzzle and raised the question: are there any other solutions that are not essentially the same. For what I mean by essentially the same, refer to that post. I still haven't figured it out, but I wanted to write about the observations I have made so far.

To recap, the standard solution is as follows: Number the coins from 0 to 63, and define the value of a board to be the bitwise xor of the numbers of the coins that are showing heads. Then regardless of the current value of the board, which we'll call \( v \), we can set the value to any desired value, which we'll call \( v' \), by flipping the coin numbered \( v \oplus v' \).

The group of numbers from 0 to 63 under bitwise xor can be thought of the group \( \mathbb{Z}_2 \times \mathbb{Z}_2 \times \mathbb{Z}_2 \times \mathbb{Z}_2 \times \mathbb{Z}_2 \times \mathbb{Z}_2 \), which is an abelian group of order 64. Each coin and square is then assigned an element of the group, and the value of a board is the product of the group elements corresponding to the coins that are showing heads.

"Aha," you might say. "Let's just replace this group with another group of order 64." That's the first thing that I thought as well, but unfortunately it turns out that this is the only group that works with this strategy. Let's start by defining exactly what our strategy is:

Let \( G \) be a group of order 64, and number its elements \( g_0, \ldots, g_{63} \) in some order. Define the value of a board to be \( \prod g_i \) where the product ranges over the coins that are showing heads in increasing index order. We are looking for such a group and numbering such that the set of values reachable by flipping exactly one coin from any given board is the entire group.

We'll prove that there is only one such group \( G \) (although any numbering will work), which is exactly the group that we already have. The first step is noticing that every element of \( G \) will need to be its own inverse.

If such a strategy is successful, then for any element \( g \in G \), \( g^2 = e \) (\( e \) is the identity element).

Proof: Suppose otherwise, that some element were not its own inverse, so we'd have \( gh = e \) for some distinct \( g, h \). In this case, \( hg = hghh^{-1} = h(gh)h^{-1} = heh^{-1} = e \) as well, so regardless of which coin comes first in the numbering, the board with only \( g \) and \( h \) showing heads will be valued as the identity. However, the board with no heads showing is also the identity, and both of these boards are neighbors of the board with only \( g \) showing heads. Therefore, in this case, the board with only \( g \) showing heads can only have at most 63 distinct values between its neighbors, so the strategy cannot be successful.

But now we can make another observation.

Let \( G \) be a group where \( g^2 = e \) for every \( g \in G \). Then \( G \) is abelian.

Proof: Consider any two elements \( a, b \). \( (ab)^2 = e \) by assumption, which we can expand as \( abab = e \). Then we can see \( ab = a(abab)b = aababb = ba \), so these two elements commute. Since this result holds regardless of the choice of two elements, \( G \) is abelian.

And finally, by the structure theorem for finitely generated abelian groups, we can conclude the following:

If \( G \) is a finite abelian group where every element has order 2, then \( G \) is isomorphic to \( \mathbb{Z}_2^n \) for some \( n \).

Putting these all together, that means that any successful strategy of this form is based on a group that looks like \( \mathbb{Z}_2^n \). For 64 coins, that means the only choice is \( \mathbb{Z}_2^6 \), which is exactly the numbers from 0 to 63 under bitwise xor.

While this certainly puts a damper on finding an essentially different solution, it doesn't come anywhere close to proving that no essentially different solution exists. It only tells us that the narrow idea of computing values by multiplying together group elements won't get us anywhere. After realizing that, I thought about other possible ways to create a working strategy.

We can think of a strategy as coloring the vertices of the hypercube graph \( Q_n \) with \( n \) colors such that the neighbors of any vertex include all \( n \) colors. Given such a coloring, you could imagine coloring an edge connecting vertices \( v \) and \( w \) by the bitwise xor of the color of \( v \) and the color of \( w \). Under this coloring, assuming the original strategy was in fact winning, it will be the case that no two adjacent edges share a color.

This reminded me of the structure of a Cayley graph. Suppose we have a group of order \( 2^n \) with \( n \) generators, and each of the generators has order 2 (notice that we're only requiring this for the chosen generators, and not for every element of the group). Then the Cayley graph for this generator set will be a graph with \( 2^n \) vertices. Perhaps, then, with an appropriate choice of the group and generator set, we'll get a graph that is the hypercube graph \( Q_n \).

However, even if we do get the hypercube graph, not every such edge coloring corresponds to a valid vertex coloring. For that, we also need the condition that any cycle of edges has colors that xor to 0. While this angle seems to bring a large amount of potential space to explore for solutions, the constraint on cycles actually ends up narrowing it back down a lot.

This is where I am now. I still don't know whether there are any essentially different solutions to the Devil's Chessboard problem, and I've gone back and forth on my guess as to the answer several times. On the one hand, it seems like a clever choice of group and generator set will make a Cayley graph that corresponds to a valid solution, but on the other hand based on what I've tried so far it feels like the cycle constraints will force it to be equivalent to the standard xor solution once you account for the fact that you can permute colors on each half of the hypercube separately.

In the other direction, I've thought that maybe you can prove that any working strategy can be generated from a group somehow. The issue that I keep running into is that because colors can be independently permuted between the two halves, it is difficult to characterize what the group should be based on the coloring. In particular, the local structure of a coloring (in other words, the coloring of a vertex and its neighbors) is completely uninteresting, and the question is really about how those local structures glue together into a global structure.

Perhaps one of these days I'll get unstuck.