# Strategy for solving "Lights Out" puzzle

Lights Out is a grid-based puzzle where each cell has two states: on/off. You can swap the state of any cell, but when you do so, the adjacent cells (horizontally or vertically) are swapped as well. Given initial the grid with random states, the objective is to set all cells to off state.

However, I've never been able to develop a strategy of how to solve (by hand) this type of puzzle. Usually I end up switching cells at random. What kinds of strategy are available for solving this game?

There are many variations of this puzzle, but I'm only interested in the classic one.

This puzzle is available in many grid sizes. It's desirable, but not required, that the proposed strategies work on all grid sizes.

My usual (and flawed) strategy is trying to clear row after row, from the top to the bottom. Unfortunately, I end up unable to clear the last row, and then I just start swapping cells at random, or just ragequit altogether.

There is an open-source and multi-platform implementation called flip as part of Simon Tatham's Portable Puzzle Collection.

• Honestly this sounds like a better fit for the Math site than for us. Nov 17, 2010 at 23:52
• Gah, I was about to point you to that implementation of Lights Out for more information. It is able to give you a solution for any valid configuration you can concoct.
Nov 17, 2010 at 23:57
• @StrixVaria -- I thought the same thing. This is gametheory, I think. Nov 18, 2010 at 0:06
• About moving this to Math... It believe some questions are valid in more than one Stack_something site. For instance, this one makes sense in both Math and Gaming. — @badp: if you can extract some kind of strategy out of the source code, feel free to describe it in plain English! (yeah, I can look at the source, but I won't look at it right now) Nov 18, 2010 at 0:20
• @Raven: ahaha this is certainly related to math (algorithms), but it has nothing to do with game theory. It is probably a best fit for stackoverflow (or even the new theoretical CS site), but definitely not here. Nov 18, 2010 at 0:36

The method I'm about to explain technically works for any size grid, but it requires some knowledge that I don't know how to determine from scratch. If you want to do some searching online related to it, the method is generally referred to as "chasing lights" or "chasing the lights".

Start by pushing the buttons on the second row corresponding to the lit cells on the top row, then the buttons on the third row corresponding to the lit cells in the second row, etc. This is exactly what you were already doing, chasing the lights down to the bottom row, which is where the name comes from.

Now, as you know, the tricky part comes when you've got a grid that's blank except for the bottom row. At this point, the way to finalize it is to push some specific buttons on the first row corresponding to the lit cells on the bottom row, and then chase the lights down from the top again. If you pushed the right first-row buttons, when you complete the second chase, the puzzle will be solved.

As far as I know, you have to just know which buttons to push on the top row to correspond to a specific pattern that was left on the bottom row after the initial chase. If you can figure out a method of determining the right ones to push on the top, you can probably use a very similar method to generalize this to any size grid. I don't know a method for this though, so I'll, uh, leave that as an exercise to the reader.

For the classic 5x5 version of the puzzle, it turns out that there are only 7 possible patterns on the bottom row after the initial chase down, so I'm just going to list the 7 possible patterns and the corresponding first-row buttons to press for each. Buttons are numbered from left to right.

``````|--------------------+-----------------|
| Left on bottom row | Push on top row |
|--------------------+-----------------|
| 1, 2, 3            |               2 |
| 1, 2, 4, 5         |               3 |
| 1, 3, 4            |               5 |
| 1, 5               |            1, 2 |
| 2, 3, 5            |               1 |
| 2, 4               |            1, 4 |
| 3, 4, 5            |               4 |
|--------------------+-----------------|
``````

Similar lookup tables can probably be found for the other sizes online.

• Since I came upon this is that solution, I have a way of determining this table: 1. try each single location at the top row individually, and see what it propagates to. 2. Since these solutions stack, you can then combine them (you could use them as rows in a gaussian elimination, for example) to solve the linear algebra equation corresponding to solving for the set you need. As an example (though not a useful one; your table has the minimal solutions already), [1,5] is solved by (1,2), and [2,4] is solved by (1,4) (from the table). Thus, [1,2,4,5] is solved by (2,4). Oct 7, 2013 at 4:14
• The row tables can be determined efficiently using Fibonacci polynomials over the binary field GF(2). See my answer.
– qwr
Apr 10 at 7:46
• It's often quicker (2-3 clicks) to do the final row manually, rather than doing another round of chasing. Apr 11 at 15:23

I don't have a strategy, but here are a few facts about the 5×5 board:

• Order does not count. Clicking on a tile A, then clicking on a tile B is exactly the same thing as clicking on tile B, then clicking on tile A — or clicking on tile A, then tile B, then tile A again, then again tile A, then maybe flipping some other tile, then tile B.
In short, a tile either is or is not part of the solution (an unordered set of tiles you must switch). Going in circles trying the same moves over and over again does not get you anywhere.

So close, and yet so far…

• Less is not more. Attempting to minimize the amount of lit/unlit cells can be counterproductive (see picture above). You should instead try to bring the game to a configuration you can recognise and solve by memory.
• Symmetric games have symmetric solutions. Keep that in mind: mirror your moves and the game complexity will go down considerably.
• Solutions are not unique, and the center tile is never required. Although it may make it easier to solve a puzzle, it appears that all solvable games can be solved without the center tile.
• "Symmetric games have symmetric solutions" -- reminds me of this: A math professor walks into his classroom to find an empty bucket and his desk on fire. He sizes up the situation, snaps his fingers, and grabs the bucket. The teacher fills it with water, and puts out his desk. The next day, the same math teacher walks in to find his desk on fire again, except this time, the bucket already has water in it. He thinks for a bit, then kicks the bucket, emptying out it's contents, thereby reducing the problem to one he had already solved. The prof. fills the bucket with water, and saves his desk. Nov 18, 2010 at 2:46
• @Raven - Interesting variation of the engineer/physicist/mathematician joke Nov 18, 2010 at 15:37
• @badp I take issue with that symmetric games have symmetric solutions. It has no basis in reality (witness Fermat's Last Theorem). Lights Out does not have a symmetric solution. Look at orion.math.iastate.edu:80/burkardt/puzzles/… Nov 22, 2010 at 5:03
• @John That said, I'm confused. Given those null solutions, how do you solve this game: [0,0,0,0,0],[0,0,1,0,0],[0,1,1,1,0],[0,0,1,0,0],[0,0,0,0,0], which you can obviously solve by clicking on the center tile, a solution that cannot be reached by combination of those null solutions. (I'm not saying you can't. Just wondering what the other solution is.)
Nov 22, 2010 at 7:00
• I think the reason 5x5 lights out is so captivating is that people look for symmetric solutions and fail. The other dimensions have more symmetry. Nov 22, 2010 at 14:17

The following solution works for every m × n grid:

Think of the given grid as a vector in a m × n dimensional vector space. Every value is either 1 (if the light is on) or 0 (if the light is off). Now you can think of every cell-push as a vector in this vector space. As you can push m x n different cells, you have m x n different vectors. If they change something in a cell, the value is 1, else 0.

As badp mentioned, it is only interesting if you have to push one button or not. No need to look at the order, no need of pushing a button more than once. So you have an equation

vector for your grid = a_1 x cellvector1 + a_2 x cellvector_2 + ... a_mn x cellvector_mn a_1, a_2, ..., a_mn is either 0 or 1.

As you have m x n variables (a_1 ... a_mn) and m x n equations (the rows of the vectors) you can solve it with Gaussian elimination.

If you are German, you might want to read "Aufgabe 2, 30. Bundeswettberwerb Informatik"

Solution to the 6x6 Lights Out:
The bottom row of a 6x6 puzzle can contain any possible combination of lights. Therefore, a table, similar to the one Chad Birch provided above for the 5x5 puzzle, would contain 63 rows. However, you can solve any 6x6 Lights Out puzzle with this small table:

``````|--------------------+-----------------|
| Left on bottom row | Push on top row |
|--------------------+-----------------|
| 1                  |            1, 3 |
| 2                  |               4 |
| 3                  |            1, 5 |
| 4                  |            2, 6 |
| 5                  |               3 |
| 6                  |            4, 6 |
|--------------------+-----------------|
``````

For any combination of lights left on the bottom row, simply combine lines from the above table, remembering that pushing a button twice is the same as not pushing it at all. For example, if the bottom row contains
4, 5, 6
you would push
2, 6, 3, 4, 6
or simply
2, 3, 4,
since the two 6s cancel.

• why this works? Apr 21, 2019 at 13:42
• This works because each button on the top row toggles a set of buttons on the bottom row (1 toggles 1 and 5; 2 toggles 2, 4, and 6; 3 toogles 5; 4 toggles 2; 5 toggles 1, 3, and 5, and 6 toggles 2 and 6). From this the table above is easily derived (e.g, pressing 1 toggles 1 and 5, and pressing 3 toggles 5, so the net effect of pressing 1 and 3 is to toggle only 1). The table works because the effects of each button add, and two toggles of the same position cancel. Apr 22, 2019 at 14:21

Playing about with different sizes of game I found a few things that piqued my curiosity.

Firstly, the 4 x 4 case is trivial - chase the lit squares down and it solves on the first pass. The 2 x 2 and 3 x 3 cases are (curiously) less trivial but not exactly hard.

Second, the 9 x 9 case is next to trivial. If we number the columns 1 to 9 (left to right in my head but either is fine of course) then there are just two results after the first chase down - either it is solved at first pass (like the 4 x 4 case) or alternatively the lit squares on the bottom row are 1, 3, 5, 7, 9 and if you now click those squares in the top row and chase those down it solves.

The 7 x 7 case seems to give in to a very simple strategy which took me about a dozen games to spot. The first chase down ends up with all sorts of different configurations in the bottom line - too many to catalogue sensibly. However, after that first chase down, I can reliably choose the top line as follows: for each square i on the bottom row that is lit you need to click on the top row squares i-1, i , i+1. You can either just click them according to that rule or write it out for the whole row and then just click those boxes that occur an odd number of times - same thing but on paper. After that chase down the squares and the job is done. Clearly if square 1 or square 7 is lit then the results are 1,2 or 6,7 as there is no 0 or 8. It still works.

At this point I tried this strategy on some other dimensions, 6, 8, 11, 12, 16 - and it does not work on them so its peculiar to the 7 x 7 case or perhaps the 7 x 7 strategy is a special case of a more general method.

Now we just need solutions for a 4x4 with wrapping. An example: {0000} {0000} {0000} {0000} Pressing the top left corner, you get: {1101} {1000} {0000} {1000} Yes, I know I started with all lights off, but it was an example. But, to follow guidelines, I have checked a few 7x7 solutions with another given method here, some are unsolvable. I am currently in the middle of creating a table for a 4x4 matrix, as I have gotten some where I had to "chase the lights" twice or more.

``````Here is the example in matrix form.
0000
0000
0000
0000 PRESS TOP LEFT

1101
1000
0000
1000
``````

See what I mean by wrapping? Just ask, and I'll reply with an answer to a press with wrapping.

• This might be too late to ask, but do you mind showing a solution with wrapping (for a 5x5 would be even better!) Dec 28, 2015 at 0:36

This puzzle is shown in the DDO quest the shroud and is very easy to solve for 3x3 - 4x4 and 5x5

4x4 is simple as it solves with just 1 pass 3x3 and 5x5 require a 2nd pass with some instructions

1st for either pass, simply click the toggle immediately below any lit spots on the top row repeat this until you reach the bottom

For 4x4 your problem is solved

For 3x3 this will leave you with lights on in the bottom row, and no matter if it is 3x3 or 5x5 you focus just on the bottom spots on the left (ignoring any on the right 2 spots on 5x5)

Now the fun part

You go back to the top row in the same column as the lit spots in the bottom 3

For the ones in column 1, you press the toggle in 1 and 2

For one in column 3, it's 2 and 3

For one in column 2, it's 1, 2 & 3

You repeat this for each lit spot, even if that means repeating to toggle the same

So X X 0 would be 1, 2 then 1, 2, 3 X 0 X would be 1, 2 then 2, 3

Etc

Then once done, solve down for a final pass and job done

A fully manual way to solve 3x3 4x4 and 5x5 puzzles

To summarize the basic linear algebra solution: For a m x n board, let A be the mn x mn binary adjacency matrix describing how lights are toggled. Then the initial state y has a solution (sequence of activations) when

``````Ax = y
``````

has a solution x over the binary field GF(2). From here it's easy to see we can solve for a particular y with Gaussian elimination, and the board is completely solvable (solvable from any initial state) iff A is invertible in GF(2).

Actually, it is possible to do much better than Gaussian elimination with row-by-row "light chasing", computing rows using Fibonacci polynomials; see J. Goldwasser, W. Klostermeyer, and G. Trapp, Characterizing Switch Setting Problems, Linear and Multilinear Algebra, 43:1–3 (1997) 121–136. (Credit to Alex Ravsky's answer for more details.)

I have proven to my satisfaction that none of the solutions given here are valid. In fact, there are 5x5 cases that are totally insolvable. Here's how you can prove it to yourself: Take a pack of cards and deal out a matrix using red cards to indicate a light on and black cards to indicate lights off. Deal any size matrix you like, and then try the technique given here. I tried a 5x5 matrix and came up with a bottom row that does NOT match the one posted here. That means that 5x5 matrix is insolvable using the "follow the lights" algorithm. Another site claims that the 6x6 matrix is always solvable. Again, using the method described above - dealing cards to create the matrix and using the "follow the lights" algorithm, I found several 6x6 matrices that were not solvable using this technique. You can site all the math you want but in practicality, THE SOLUTIONS GIVEN HERE DO NOT WORK FOR ALL MATRICES.

This is because only 25 percent of all games are solvable. Those that are solvable wil be solvable with that methode.

• You're saying a strategy is invalid because it won't let you solve unsolvable puzzles? It's good to make it clear that some lights-out configurations are unsolvable -- and so they're not valid lights-out puzzles. But presumably the techniques proposed for solving lights-out puzzles are intended for valid (i.e. solvable) ones. Jan 11, 2017 at 18:52