Strategy for solving "Lights Out" puzzle

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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"

Answer 4

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.

Answer 5

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.

Answer 6

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.

Answer 7

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

Answer 8

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.)

Answer 9

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.

Answer 10

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.