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.

  • 10
    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.
    – badp
    Nov 17, 2010 at 23:57
  • 1
    @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
  • 1
    @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

10 Answers 10


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.

  • 2
    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).
    – zebediah49
    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, 2022 at 7:46
  • It's often quicker (2-3 clicks) to do the final row manually, rather than doing another round of chasing.
    – OrangeDog
    Apr 11, 2022 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.

    1 unlit cell, 11 moves away.
    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.
  • 6
    "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
    – Nick T
    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/…
    – John Smith
    Nov 22, 2010 at 5:03
  • 1
    @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.)
    – badp
    Nov 22, 2010 at 7:00
  • 1
    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.
    – John Smith
    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.
    – John Herro
    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.


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!)
    – DeanAttali
    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


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 am having some trouble with advanced math. Is there some simpler way to determine what to toggle on the first row depending on the last row config without a predetermined table? Some "mechanical" method a 10 year old, or even maybe a 7 year old, could do, even if it takes longer? Such as maybe, somehow, working back from the last row on to the top row using a simpler method? Some formula? Thank you!
    – Gec
    Oct 17 at 22:41
  • I'm not aware of any. Maybe someone who knows more about Fibonacci polynomials can come up with a trick.
    – qwr
    Oct 17 at 23:38
  • @Gec I'll think about it and let you know if I come up with something.
    – qwr
    Oct 18 at 3:23
  • Thank you! The problem is definitely more complex than it seems. One might expect to be able to work their way backwards, but that seems impossible.
    – Gec
    Oct 18 at 15:57
  • In theory you can teach 10 year olds how to do matrix multiplication and inversion mod 2, however it would be extremely tedious compared to just memorizing solutions.
    – qwr
    Oct 18 at 17:38

This method always finds the optimal solution, but is only really applicable to the 3x3 puzzle as it requires quite a bit of memorization.

First use a solver (I used the one in Simon Tatham's puzzles) to learn the solution to a few cases. The more you learn the easier solving from any case will be, I recommend any case where either 1 or 2 adjacent squares are on as these can be applied to any rotation and are quite useful.

When solving from any case, most of the time it won't be one you know how to solve, but with usually only 2 or 3 setup swaps, you can get it to a case you know how to do, if you do all the swaps that are either only in the setup swaps, or only in the solution from the case they set up to, but not the ones that are in both, it will solve the puzzle in the fewest moves possible for that case.

This can be used for larger versions of the puzzle, but would require you to memorize many more cases, each of which require more swaps, so would be much harder to learn how to do.


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.

  • 3
    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.
    – LarsH
    Jan 11, 2017 at 18:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .