Though online gaming isn’t usually my thing, my friend Alec has been a World of Warcraft nerd for many years. One day, after spending the night chatting with a fellow guildy, Alec presented me with a lights game puzzle. He writes:

I was hanging out in World of Warcraft one day, and a guildy was looking for the blue mechanowolf (Friender) pet for his Hunter. He came across the lights puzzle in Gnomeregan which summons Friender for you to tame, and was having trouble solving it. He asked for help in guild chat, and being a lover of puzzles, I decided I wanted to take a look.

The puzzle is pretty simple. You have a set of 8 lights, some of which are on, and some of which are off. If you click on a light, it toggles that light and the ones next to it. The object is to get all of the lights to be turned on. For instance, if the lights are currently set up like this:

You could click the second light, which would change the puzzle to look like this:

Unfortunately we were struggling to solve it. In fact, if you attempt to solve the example I’ve given you, you’ll find it’s impossible. Surprised that I couldn’t solve this when it seemed so simple, I took the puzzle to bed with me on a notebook, using binary representation to write out steps. Using the above example, I would have written 10110000 on my notebook with 01010000 underneath it to indicate the new sequence after clicking the second light. I finally gave up around 3:00 AM, extremely frustrated.

The next morning, I went into work and decided I was going to ask my co-worker Jon about this. I was fairly certain that there was no solution to the puzzle, but I wanted to ask him if there was a way to prove mathematically that the starting sequence I was working with (say 10110000) was impossible to manipulate to 11111111 given the rules of the puzzle.

After thinking about the problem for a while, I found that Alec was indeed correct. In particular, 1/2 of the starting configurations for the lights game have no solution! My reasoning is as follows:

Imagining each light to be independent of any other,
the 8 lights can be in any of 256 configurations, 2^8.
I aim to show that the 8 light operations in the light
game are dependent on one another and therefore not all
256 configurations can be reached from any other.
Further, from any starting configuration, only half of
the configurations, 2^7 = 128, can be reached.

Let us begin by considering the independent case.
Each light can be in any of two states, either on
or off. For modeling purposes let us assign the
number 1 to an on state and 0 to an off state.
Also, let us assign the function `add 1 modulo 2`,
which we will denote (+ 1), to the act of changing a single
light from its current state to its other state. In other
words we are mathematically representing the actions on a
single light as the cyclic group Z/2Z generated by (+ 1).
Effectively this means:

(a) performing (+ 1) an odd number of times affects the same
change on a light as just performing (+ 1) once. Let us denote
any performance like this with an ‘a’ for action. By parallel,
we notice that performing (+ 1) an even number of times effects
no change at all. Let us denote this trivial change by ‘e’.
Performing either ‘a’ or ‘e’ are the only two actions we can
perform on a given light, a(1) = 0 for instance.

(b) Both actions are self inverse and thus performing either
of them an even number of times is a trivial action,
a.a = e or e.e = e. This means that pairs of the same action
can be `cancelled` from a performance, ie.
(a.e.a.a.e.e.e.a)
(a.e.e.e.e.a)
(a.e.e.a)
(a.a)
(e)

(c) Possibly most crucially, performing the same actions in one
order versus another makes no difference to the outcome, ie.
(a.e.a.a.e.e.e.a) = (a.a.a.a.e.e.e.e). This last property of the
group is called the Abelian property.

Now for a leap of abstraction. While any one light can be
represented by one of our cyclic groups Z/2Z, we can also
consider pairs of Z/2Zs to represent pairs of lights (or more
generally n copies of Z/2Z can represent n many lights).
Now where elements of Z/2Z are either 1 or 0, elements of
pairs of Z/2Z can be written (0, 0), (0, 1), (1, 0), or (1, 1),
corresponding to the 4 configurations the pair of lights can
be found. Similarly, actions on these states can be written
(e, e), (e, a), (a, e), or (a, a). The act of performing paired
operations like (e, a) on paired states like (1, 1) can be
defined pairwise giving (e, a) (1, 1) = (e(1), a(1)) = (1, 0).
Notice how the nice properties (a)…(c) above extend in a rather
nice way.

(a’) Performing either (e, e), (e, a), (a, e), or (a, a) are the
only actions we can perform on a given pair of lights. Further,
(e, a) and (a, e) are generators in that combinations of these two
can be used to get to any other possible state.

(b’) Each action is self inverse.

(c’) This newly formed group of pairs has the Abelian property.

This suggests more generally that for n lights we can construct
an n-fold Abelian group whose elements (a1 … an) designate
any of 2^n possible light configurations and whose actions
(f1 … fn) designate any of 2^n possible ways to effect n lights.
Notice, that this model preserves the independence of any given
light. In other words, the only way to change the light in the jth
place in the a list, (a1…aj…an) is by having fj be an ‘a’.
pictorially,

This fact has far-reaching consequences for us. If we are to write
out each of the n generators for the n-fold Abelian group,
f1 = (a e e … e)
f2 = (e a e … e)
f3 = (e e a … e)
…
fn = (e e e … a)

Not one of them can be expressed as the combination of any of
the others. Changing the jth and kth light has no effect on the mth.
These n independent actions form what is called a basis for our group.
That no action can be written as the sum of any others also means
that from any configuration on n lights we can get to any of 2^n
light configurations by applying combinations of the n actions.
With 8 lights, for instance, we can get to any of 2^8 = 256
configurations via combinations of the 8 basis actions.

If, on the other hand, the actions were dependent so that some
action, fj, could be performed as the combination of any of the
others, fj = f1.f3.f2 say, so would any performance involving fj
be dependent on a combination of f1.f3.f2. This means that we
could only reach 2^(n-1) possible configurations, 2^7 = 128 in
our example.

Now for the punchline (no longer the independent case but rather
the actual case). The light game has 8 possible actions. Each action
effects a small handful of lights. Changing the leftmost light, for
example, also effects its next closest neighbor to the right.
Generally, changing any light also effects that lights nearest adjacent
lights. If these actions were independent, they could be used to
reach any of 256 configurations for any starting configuration.
If instead we can perform any action as the combination of any others,
we can then only reach 128 configurations, ie half of the possible
configurations.

Notice, that performing (f1.f5.f4.f2.f7) as above, is the same as
performing f8. This means that f8 is dependent on f1, f5, f4, f2,
and f7. Via the reasoning above, this means that f8 does not contribute
uniquely to arriving at any configurations we otherwise could get to using
the other actions and therefore the total number of configurations
we can arrive at with f1 through f7 is 128, ie. less than 256.

Of course we could have instead thought of the 8 operations as being a basis for a vector space and considered them as the rows of a matrix. Then by computing Gaussian elimination we would see that only 7 of these vectors form a basis, ie. one of the rows would be zero. Further, the 7 vectors form a basis for a space with 128 elements. This means that for any given initial configuration, only 1/2 of the total configurations can be reached, as is intended to be shown.

Lastly, this particular puzzle reappears in a different form later on in the game. There it appears as the Shaman’s Totem puzzle. Though the game pictorially has been extended to a 2-dimensional playing field, the mathematics works out the same. Here instead of 8 lights there are 25 lights. Encoding these as binary vectors and computing Gaussian elimination gives the basis for the space of accessible light configurations, which btw IS fully accessible for any starting configuration 😉

• Conjecture: Light games with n lights where n is congruent to 0 or 1 modulo 3 are completely solvable.