How to beat 'Lights Out' using basic Linear Algebra:

In 1995, Tiger Electronics released an electronic game called 'Lights Out'. The game is played on a 5-by-5 grid as it is in the title image. The game starts by randomly switching on any/all of these 25 lights. The objective of the game is straightforward. We need to turn them all off (sometimes with the restriction on the number of grids you click). The kicker is that when you click a grid, it not only toggles the state of that grid but also its immediate neighbors(the grids sharing an edge). An example of a game is shown below:

The yellow light in my version of the game indicates where the cursor is so it is easy to follow along the grids being clicked. If you want to play the game before reading further, check out this link that I got from a Google search.

How do we tackle this game using Linear Algebra?

Initial Observations:

• The order in which you click the grid does not matter.
• Clicking a grid twice undo the changes made by its first click so there is no reason to click a grid twice.
• A sequence of buttons needed to be pressed to bring out a light pattern is the same as the buttons needed to be pressed to turn off all the lights in that pattern.

These three observations are good enough for us to formulate our ideas.

Lights Out: 3-by-3

In the following discussions, we only deal with a 3-by-3 version of the game for simplicity. The ideas transfer over to any 'n by n' grid.

Notice that the initial pattern of lights in the puzzle can be thought of as a vector/array of 1s and 0s. An example is given below and we name it as game_array:

We can also encode the action of clicking a grid as an array as well. Imagine you are playing the 3-by-3 version with the above initial pattern. What happens when you click the middle grid? Let's see:

In general, we know exactly what happens when we click the middle grid. It toggles a total of 5 grid lights which can be expressed as an array named action_array:

When we click the middle grid in this puzzle we discussed above, it should toggle the state of the light: 2, 4, 5, 6, 8 in the game_array. Computationally, we can think of this as the addition of game_array and action_array in the finite field of order 2 (or) element-wise XOR operation on these two arrays. By addition, we always mean either of the above operations.

However, you won't just use the middle grid so you have 9 different action_array acting on the game_array. If we put all of these action_arrays together, we get an action matrix of size 9-by-9. Clicking the i-th grid is the same as multiplying a vector of size 9-by-1 with 1 in its i-th position. The translation of clicking the middle grid is shown below using matrices:

Technically, with the way I described this action matrix, the matrix product should look different. It should be a 1-by-9 array multiplied to this matrix and the result is another 1-by-9 array. The reason the above equation in the picture is also true comes from the fact that this matrix is symmetric. Meaning, that if I switch all rows to columns and vice versa, the matrix remains unchanged.

Application of Linear Algebra:

Let us call the action matrix 'A'. We know from the third observation that to turn off all the lights in a given light sequence, we need to find the grids that need to be clicked to make that pattern. So, game_array should be our output from the matrix multiplication. We just need to find the array 'x' which represents the solution (grids need to be clicked).

How do we find x?

Well, we need to find the inverse of the matrix A and multiply it with the game_array. But, keep in mind that you are inverting this matrix in the binary world which is the finite field of order 2. When you google 'online inverse of a matrix', the links provided most likely invert the matrix in the field of Real numbers. We can use any free computer algebra system (I used Macaulay2) to compute this in an instant.

If the inverse exists, then:

But, is A invertible?

Turns out for the 3-by-3 case, A is indeed invertible which makes our life super easy. The following image shows the inverse of A and also the solution to the puzzle we started.

Thats it! We solve this puzzle minimally by pressing the grids: 1,3,5,6,8. The animation below proves it visually.

Since the inverse of A exists for the 3-by-3 case, not only that any light pattern is solvable (511 possible light patterns), but also the solution is unique. Meaning, you can only click these 5 grids (in any order) to solve this pattern.

A practical way to solve:

Well, if you have a program ready to invert a 9-by-9 matrix and to do matrix multiplication, this is indeed easy. This isn't practical if someone puts you in a spot to solve the puzzle. Can we do better?

Indeed, we can!

Algorithm: To turn off lit grids in top rows, press the grid immidiately below the lit ones. Continue until only the bottom row has lit grids.

A demo using the same example:

You can see that this guarantees only lit grids in the bottom row. It is not surprising that this algorithm is incomplete and inefficient (we still have 6 ideal moves to complete the puzzle). Nevertheless, we made a good observation. Indeed, we only need to learn/solve the patterns in the last row.

With this observation, we can reduce the size of our action matrix significantly.

How exactly!?

We only need to figure out what happens in the last row when we press a grid in the first row and follow the algorithm until only the grids are lit in the last row. How does this action matrix look like?

We start by seeing what happens if we click the first grid in the first row and do the algorithm.

The animation above tells you that clicking the first grid and doing this algorithm will only activate the last two grids in the last row. So, it would be encoded as an action array with value: [0,1,1]. We similarly find the action arrays for the other two grids in the top row (shown below).

This will give us a 3-by-3 action matrix and we can easily invert that (even by hand) to solve the puzzle.

We have all the tools to solve the puzzle(game_array) we started. We chased the lights down (animation after the algorithm introduction) to the bottom row where it lit the 1st and the 3rd grid in the last row ([1,0,1]). So, we need to know which buttons in the top button need to be clicked (and follow the algorithm) to turn on grids 7 and 9 (1st and the 3rd grid in the last row).

Let us see if this is true by starting over the same puzzle(game_array).

Tada!! Even though this might not give us an optimal solution, we still managed to solve it.

You might wonder if this solution disproves our previous statement regarding the uniqueness of the solution. Well, if you look closely, we made a total of 7 moves. The optimal solution only had 5 moves. The reason for the extra 2 is that we pressed the 4th grid twice (redundant moves).

How about solving the 5-by-5 version?

As you can guess, the action matrix for the 5-by-5 version is not invertible. This immediately means that not all the possible light patterns (2^{25} - 1 = 33554431 light patterns) are solvable. However, the original game (or) the game I wrote only uses patterns that could be solved.

Since the action matrix here is non-invertible, we can observe cool things like this:

You can see that even though we did not press a grid more than once, the final state and the initial state are exactly the same. This is not possible if the action matrix is invertible.

This only means that there is more algebra to enjoy in this original version than we did in the 3-by-3. Since it touches on a couple of concepts that need to be well-visited, I am planning on writing about it in my next article.

More use cases?

Well, it turns out you can expand on this idea and can do some roundabout way of animation. The gif below shows a 60-by-60 version of the game in which the solution is programmed to not turn off all the lights but to turn on only some specific ones.

That is a picture of my beautiful wife. This is the exact game with the exact same concepts. I just sped up the auto-solver to show this transformation in a reasonable time.

Before trying this out, be ready to work with a 3600-by-3600 matrix!

Credits:

I wanted to see if there are board games that use a good bit of math. I came across the existence of this game when I visited this link. This link also contains the sequence of integers 'n' for which the 'n-by-n' version has an invertible action matrix/has a unique solution.