Solution to LightsOut

Introduction

LightsOut is a simple puzzle, consisting of a 5x5 grid, each cell of which contains a light.

You may click on the cells. Doing so changes the state of the light of that cell, and of the direct four neighbor cells (or three neighbors for edge cells, or two neighbors for corner cells)

The goal of the puzzle is to turn off all the lights, ideally in the fewest number of clicks.

I was curious how many clicks it was required, and so did the obvious thing: I wrote a brute force program to find it experimentally. The puzzle is small enough that this program only took a few seconds to run.

However, that seemed rather inelegant, so here is an attempt to solve the puzzle in a less brutish way. (It is still actually brute force in a way, but at least it appears analytical)

Preliminary Observations

• The final state of any cell after a series of moves depends only on how many times that cell and its four neighbors (three neigbors for edge cells, two neigbors for corner cells) have been clicked.

  If that total number is odd, the cell will be out. If that total numver is even, the cell will be on.

• The order of clicking does not matter.

• There is never any need to click a cell that has already been clicked.

This means that we can solve the puzzle if we can assign to each cell a number, 0 or 1, with 0 representing not being clicked, and 1 representing being clicked exactly once, such that for each cell, the sum of its number and that of its neighbors, is odd.

The First Row

Let's get started. We'll start with the first row. Since we don't know anything yet, we'll do this symbolically. Let's let A represent our action in the first cell, B our action in the second cell, and so on.

At this stage, we have no idea whether A is 1 or 0, whether B is 1 or 0, and so on. So, we'll just work with A, B, C, D, and E, working our way down the grid, and then see what we have to set these variables to in order to make everything work out.

So, this is where we are so far:

The Second Row

Let's consider now the first cell in the second row. What do we have to do there in order to make the cell above it "happy"?

Suppose the value of the first cell in the second row is X. Then the sum for the cell above is A+B+X. We want this to be 1, so that the first cell in the first row is turned off.

So, we need to solve the equation "A+B+X=1". This is easy in Odd/Even arithmetic. On OddEven arithmetic, because anything added to itself is 0, we can simply add A+B to both sides, giving "X=1+A+B".

In general, in an Odd/Even equation, you can move any variable or constant from one side of the equals sign to the other, so it is very easy to solve any equation.

How about the second cell in row 2? What X would we have to give that cell to make the second cell in the first row happy? We want B+A+C+X=1, so X=1+A+B+C.

Doing this for the rest of the second row gives us this:

On to Row Three!

Continuing on, we can work out row three. Let's start with the first cell in row three. To make the cell above happy, we need to pick X so that (1+A+B)+(A)+(1+A+B+C)+(X) is 1. I've put parenthesis around the parts that come from each cell, to make it easier to see where I'm getting these things from.

Solving for X, we get X=1+A+C.

Continuing, we get this:

...And the Rest

If we keep on going, we end up with this for the complete board:

Finding A, B, C, D and E

Because of the way we figured out the values for each cell, no matter what values we pick for A, B, C, D, and E, all the lights except the last row will be off.

Our task now is to find values for those variables that will also make the last row of lights be out.

The first step is to see what the sums are for the last row. They are:

1. B+C+E

2. 1+A+B+C

3. 1+A+B+D+E

4. 1+C+D+E

5. A+C+D

We need each of these to be 1. Let's take A+C+D. There are four different ways to make that equal 1. One way is to A, C, and D all be 1. The other three ways are to make one of the three 1 and the other two 0.

Let's do the A=1, C=1, D=1 case first. If those are all 1, then to make sum #4 work out, we need E=0. To make sum #3 work out, we need B=0. With those values, sums #2 and #1 also work out, so we have a solution!

That solution gives us this pattern of clicks:

Now let's try A=1, C=0, D=0. Sum #4 then requires E=0. Sum #3 requires B=1. Again, sums #2 and #1 work out, so we have another solution!

How about A=0, C=1, D=0? Now we must have E=1 for #4 to work, and B=1 for #3 to work. That makes #2 and #1 work, so we have yet another solution!

Finally, A=0, C=0, D=1 works, giving us E=1 and B=0.

If you plug those other solutions in, you'll see they are basically the same as the first, just rotated or reflected.