Blogs, Educational Games

Solving Lights Out!

Hopefully you have had the opportunity to try Lights Out for yourself. If not, I would suggest heading over and playing before seeing what the solutions will be, which is what we’ll be discussing in this post.

Overview

The great thing about lights out is that there are many different permutations of how the lights can be turned on or off.  Each of these gives you a new challenge, so you can continue to playing for a long time before you end up having to repeat old problems.  In particular, since any light can be turned on or off, we have two choices for each light.  Each choice gives us a different option, so there are \(2^{9}=512\) options for the \(3 \times 3\) board and \(2^{25}=33,554,432\) options for the \(5 \times 5\).  On the other hand, if we use the dimmer option, we will have \(3^{9}=19,863\) and \(3^{25}=847,288,609,443\) different layouts, respectively.

If you have been playing both the \(3\times 3\) and \(5 \times 5\) boards, with or without the dimmer option you would have already noticed the difference in difficulty.  More possible layouts of the board leads to having to account for these different options, and therefore increases the difficulty.  Ideally, we would like to be able to provide a solution for any of these options; however, trying a brute force technique seems extremely daunting.  Therefore, I will try to limit the number of cases we have to consider.

Limiting options

To begin with, we have already studied these symmetries in Symmetry of regular polygons.  Using the information found there, we will note that there are 8 different symmetries of the square.  Therefore, if we can find a solution to one permutation of lights, it will give us the other corresponding 7 solutions.  Some of these symmetries may be the same permutation of lights, so we can’t quite just divide by 8.  An example of this would be that if only the middle light was on, all 8 symmetries would result in the same permutation of lights.  Whereas, if only the top right was on, this would lead to 4 distinct permutations of lights. (See pictures below).

Middle Light

 

4 equivalent options under symmetry

The variable number of permutations per symmetry makes trying to count up our options at this point difficult.  We will instead look at another way to remove options.  Here, I will note that, if we can find a way to change exactly 1 light, then a solution for when this light is off will give us a solution for when the light is on.  This is particular useful when there is only 1 light on, because the solution when it is off is to do nothing.  Furthermore, if we knew how to change another light without changing anything else, we would have a solution for both lights being.  Continuing this argument, we see that instead of trying to find solutions to all possible light permutations, we will instead look for solutions to any possible way to have exactly 1 light on at a time.  If we can find all of these, then by combing the solutions, we can solve any permutation.

Now, since we will only be dealing with 1 light at a time, we can count the symmetries of each case.  For example, if only the middle light of a \(3 \times 3\) is on, this will correspond to only this case.  If we have only the upper corner light on, this will be equivalent, through symmetry, to any corner being lit.  Therefore, in either the \(3 \times 3\) and \(5 \times t\) we can drastically limit the number of specific cases we have to look at.

3×3-On/Off

For the \(3\times 3\) case we have already found two light permutations we will need a solution for.  Another case that can arise is the outer middle light can be on and all other off.   There are four of these options that, through symmetry, are equivalent.  We then have 9 total options for a single light being on or off, so this would be all possibilities for the case without a dimmer.  Therefore, we can find all the solutions if and only if we can find these three.

Corner

The first case we will look at is when the upper left corner light is on (see below).  Now, in order to find the solution to this case, the most obvious method is trial and error.  In this case, we play the game until we can find a pattern that will only change the upper left corner light.  If you would like the opportunity to find this on your own, head over to Lights Out before scrolling down.

Upper Left Corner

What we find is that if we hit the buttons as described in the table below, we will alternate only the upper left corner.  Check this out for yourself.

1 0 1
0 0 1
1 1 0

Outer Middle

The next case we will consider is when one of the outer middle lights is on (see below).  In this case, again, we will use trial and error in order to find the solution.  Doing this, we get the following solution.

Outer Middle Light
0 0 1
0 1 1
0 0 1

Middle

The last case we will consider is when one of the middle light is the only one on (see below).  In this case, again, we will use trial and error in order to find the solution.  Doing this, we get the following solution.

Middle Light
0 0 1
0 1 1
0 0 1

With the dimmer on, we have a few more options to deal with.  That is, in addition to a light being on or off, it can also be dimmed.  In our version, we go from off to on to dim then off represented by black, green and red.

However, if we can do the same 3 options with the light dim or on, we will again get all solutions by combining these.  We also notice here that turning the switch twice is the same as go backwards on the turn once.  Therefore, if we know the solution when the light is on, we can perform this pattern twice in order to get the solution for when the light is dim.  Again, we will only have three cases to show.

With the dimmer switch on, it will take more tries to find the solution.  However, you can still find the solutions through trial and error.  I highly encourage you to try this for yourself, as finding these patterns is the fun part.  I will also provide tables for the 3 cases we considered above with the lights fully on.

Corner

What we find is that if we hit the buttons as described in the table below, we will alternate only the upper left corner.  Check this out for yourself.

1 2 1
2 2 0
1 0 0

Outer Middle

The next case we will consider is when one of the outer middle lights is on.  In this case, again, we will use trial and error in order to find the solution.  Doing this, we get the following solution.

2 2 0
2 2 1
2 2 0

Middle

The last case we need to look at is when the middle light is the only one on. Again, through trial and error, we will find our solution.

2 2 2
2 0 2
2 2 2

Conclusion

We were able to take a puzzle with a large number of different possibilities and find all the solutions.  The process used here is quite typical when dealing when any type of mathematical problem.  That is, we worked with the problem so that we didn’t have to proceed by brute force.  Rather, we could use inherent properties of the puzzle to come up with a much smaller list of problems we would have to solve.  Once we did this, we were then left with having to find a solution any way we could.  In this case trial and error seemed to be the best way.

This is the true educational value to such games.  That is, the games can really help by giving you a reason to find a few solutions.   Hopefully you can then start to generalize the patterns that you see, so that you can start to beat the game regardless of what it throws at you.  Eventually, you can then beat a game that seemed like it would offer endless possibilities.  While the setting may seem trivial, the process involved is the very core of what occurs in mathematical proofs.

If you learned something from and enjoyed this post, please like it below.  Also be sure to follow us here or on social media so that you know when new posts are made.  If you’d like try out the solutions, head over to Lights Out.  I’ve added the ability to edit one light at a time, in case you want to work with specific examples.  If you get lost on a \(3 \times 3\) puzzle, you can also hit the solve button to see the solution.

More to do

I have not enabled the solve option for the \(5 \times 5\) yet for two reasons.  First I want to give you the opportunity to have fun and find the solutions yourself.  Secondly, I haven’t actually found them yet.  If you find any patterns for the \(5 \times 5\) feel free to leave a comment giving your solution.  Once, we find all the needed ones, I update the solve button to work on these.  Have fun!

1 thought on “Solving Lights Out!”

We'd love to hear your thoughts!

This site uses Akismet to reduce spam. Learn how your comment data is processed.