This week’s Riddler Classic is a variant of the familiar hat color guessing game with a twist. Here the four participants are on the corners of a square and can only see hats of their neighbor’s along the edges of the square they are connected to. The challenge is to come up with a strategy for the players to guess the color of their own hats that guarantees at least one of the players correctly guesses their hat color, no matter what combination of the three colors of hats are placed on the four players. Since there are no restrictions on the hat colors or placements there are 3^4 or 91 possible games to make sure we have at least one winner for.

One question we can ask right away is: “why should it be possible to do this at all?” It is not immediately obvious that it is the case, however there are similar games where it is the case. One way to analyze these games is to try to understand the strategy from the bottom up. Here we will take a more general computational search approach which will allow us to solve for strategies with larger N, different shape polygons, etc in the future.

We note that each of the players (labeled clockwise V1, V2, V3, V4) can only use information from two other players’ hats. V1 can only use information from V4 and V2, V2 from V1 and V3, V3 from V2 and V4, and V4 from V3 and V1. We notice also that players on diagonally opposite corner of the square have the same information to work with.

We will define strategies for the player as a function of the other players that they can see: ie S(V1) = f(V4,V2), S(V2) = g(V1,V3), S(V3) = h(V2,V4), S(V4) = i(V3,V1). Note that the arguments are ordered clockwise around the square, with the trailing vertex first in the argument list.

Now, there are a lot of possible functions out there. First we will try something simple: f(Vn,Vm) = [ (+/-) Vn (+/-) Vm] %3, where the (+/-) terms can take either + or – values. This has the advantages of 1) symmetrically weighting the players 2) the 3-color modulo guarantees a mapping to a possible color 3) some history of success in hat problem land!

We code up some Python to try all combinations of (+/-) (256) acrosss all possible games (91). We do not attempt to reduce the dimensionality as the problem is still small enough to do an exhaustive search:

We find two possible, very similar, distinct strategies (adjusting for rotationally identical ones). Note we have labeled colors [0,1,2]. There are 9 game variants where all the players guess correctly, but in 72 cases only one player guesses correctly:

Solutions for Other Values of N

We searched for solutions for other values of n = (3,5,6,7,8,9) using this simple functional form and had no luck. We upgraded the code to allow strategy functions of the form: f(Vn,Vm) = [ (+/-) Vn (+/-) Vm (+/-) offset] %3, where the offset term can be k or 0.

Setting the offset term to 1 or 0 we find many solutions to the n=3 problem with one correct player guess per game, which is of course enough to win. This sample is typical: