Take the 2-minute tour ×
Arqade is a question and answer site for passionate videogamers on all platforms. It's 100% free, no registration required.

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.

share|improve this question
7  
Honestly this sounds like a better fit for the Math site than for us. –  StrixVaria Nov 17 '10 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 '10 at 23:57
    
@StrixVaria -- I thought the same thing. This is gametheory, I think. –  Raven Dreamer Nov 18 '10 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) –  Denilson Sá Nov 18 '10 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. –  BlueRaja - Danny Pflughoeft Nov 18 '10 at 0:36

5 Answers 5

up vote 12 down vote accepted

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.

share|improve this answer
1  
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 '13 at 4:14

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.
share|improve this answer
3  
"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. –  Raven Dreamer Nov 18 '10 at 2:46
    
@Raven - Interesting variation of the engineer/physicist/mathematician joke –  Nick T Nov 18 '10 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 '10 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 '10 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 '10 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*n different cells, you have m*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 * cellvector1 + a_2 * cellvector_2 + ... a_mn * cellvector_mn a_1, a_2, ..., a_mn is either 0 or 1.

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

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.