Solving Lights Out

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

User avatar
Robert'); DROP TABLE *;
Posts: 730
Joined: Mon Sep 08, 2008 6:46 pm UTC
Location: in ur fieldz

Solving Lights Out

Postby Robert'); DROP TABLE *; » Thu Jul 12, 2012 11:09 pm UTC

I'm trying to find a algorithmic way to solve this game, and I got some way to a solution, but then got stuck.

First, I decided that I could simplify the problem by, instead of trying to go from any state to any state, going from some beginning state to an empty board. (And then, if needed, from the empty board to some other state, since the moves are invertible.) So I called the initial state of the square (x,y) Gxy.
Then, I managed to prove that pressing the same button twice has no effect, and order doesn't matter. From there, I imagined a grid, S, representing the moves that take me from the state G to an empty board. Every member of this grid is either 0 or 1, and it's the same size as G.
This means I wind up with a set of equations:
Gxy = Sxy + S(x-1)y + S(x+1)y + Sx(y-1) + Sx(y+1)
(Defaulting to 0 if Sxy doesn't actually exist.)

However, since I have 25 of these equations, I have no idea how to solve them in a way that's at all methodical. Can anyone here help?
...And that is how we know the Earth to be banana-shaped.

User avatar
Snark
Posts: 425
Joined: Mon Feb 27, 2012 3:22 pm UTC

Re: Solving Lights Out

Postby Snark » Thu Jul 12, 2012 11:16 pm UTC

Are you trying to find the best possible solution (fewest number of moves)? Or just any solution?
Dashboard Confessional wrote:I want to give you whatever you need. What is it you need? Is it within me?


Avatar by Matt

Giallo
Posts: 226
Joined: Sat Jan 01, 2011 11:31 pm UTC
Location: ETH, Zürich, Switzerland
Contact:

Re: Solving Lights Out

Postby Giallo » Thu Jul 12, 2012 11:22 pm UTC

Well... 25 equations, 25 unknowns and (almost surely) the equations are linearly independent. I'd say that matlab/python/mathematica could help you ;)

Also, I think the solutions are unique (up to double clicks of the same button).

An alternative possibility would be to try to find an algorithm to turn only one light on and then sum up the moves and reducing modulo 2 (since order does not count).
"Ich bin ein Teil von jener Kraft, die stets das Böse will und stets das Gute schafft."

User avatar
Robert'); DROP TABLE *;
Posts: 730
Joined: Mon Sep 08, 2008 6:46 pm UTC
Location: in ur fieldz

Re: Solving Lights Out

Postby Robert'); DROP TABLE *; » Thu Jul 12, 2012 11:54 pm UTC

Snark wrote:Are you trying to find the best possible solution (fewest number of moves)? Or just any solution?

Any solution will do, although I suspect solutions will be unique, as Giallo mentioned.

Giallo wrote:Well... 25 equations, 25 unknowns and (almost surely) the equations are linearly independent. I'd say that matlab/python/mathematica could help you ;)

I also tried this, but couldn't work out how to interpret the result. Asking Python to solve a grid of all lights being switched on yields a "solution" of

Code: Select all

[0.36, 0.32, 0.23, 0.32, 0.36]
[0.32, 0.23, 0.32, 0.36, 0.32]
[0.23, 0.32, 0.36, 0.32, 0.09]
[0.32, 0.36, 0.32, 0.09, 0.14]
[0.36, 0.32, 0.09, 0.14, 0.09]

(Rounded to 2 d.p.)
Since none of those are 1 or 0, I'm not precisely sure what they mean. (I can post the entire program I used to get that solution, if it's at all helpful.)
...And that is how we know the Earth to be banana-shaped.

Nitrodon
Posts: 497
Joined: Wed Dec 19, 2007 5:11 pm UTC

Re: Solving Lights Out

Postby Nitrodon » Fri Jul 13, 2012 12:20 am UTC

The following sequence of moves also does nothing, so the equations are not linearly independent:

Code: Select all

*.*.*
*.*.*
.....
*.*.*
*.*.*


As for solving those equations, remember that they hold over the field of integers modulo 2, and not in the reals. If you solve the system of equations over the reals instead, the result will be meaningless.

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Solving Lights Out

Postby jaap » Fri Jul 13, 2012 7:27 am UTC

Nitrodon wrote:The following sequence of moves also does nothing, so the equations are not linearly independent:

Code: Select all

*.*.*
*.*.*
.....
*.*.*
*.*.*


As for solving those equations, remember that they hold over the field of integers modulo 2, and not in the reals. If you solve the system of equations over the reals instead, the result will be meaningless.


There is this pattern, and the same pattern rotated by 90 degrees. So of the 25 equations, there are (at least) two superfluous ones. It turns out that there aren't any dependencies, so you actually have 23 linearly independent equations in 25 unknowns. You can solve the set of (25 or 23) simultaneous equations using ordinary methods as long as you remember that you are working in the integers mod 2. This means that for any of the variables, x+x = 2x = 0x = 0. Similarly if you add the equations x+y+z=1 and w+x=1 together, you get w+y+z=0.

Solving simultaneous linear equations is linear algebra, and is generally easier if you use matrices and vectors rather than separate equations and variables.

Anyway, if you feel like delving deeper into the specifics of the maths behind Lights Out, have a look at my theory page.

mfb
Posts: 950
Joined: Thu Jan 08, 2009 7:48 pm UTC

Re: Solving Lights Out

Postby mfb » Fri Jul 13, 2012 12:37 pm UTC

Two other ways to reduce the problem:
- solve how to switch off a single light (I did not check if this is a valid game state). As the system is linear, multiple lights are just the sum of the individual solutions. Apart from symmetry, there are just 6 cases to study.
- fixing the 5 switches of a single edge gives a direct way to determine the other 20 switches row by row. Therefore, you can simply try all 32 combinations, some of them have to work.

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Solving Lights Out

Postby jaap » Fri Jul 13, 2012 12:55 pm UTC

mfb wrote:- solve how to switch off a single light (I did not check if this is a valid game state). As the system is linear, multiple lights are just the sum of the individual solutions. Apart from symmetry, there are just 6 cases to study.

Earlier in the thread it has already been shown that the equations are not independent. It follows that not every light can be independently switched.
It turns out that only the centre light and the four lights diagonally adjacent to the centre can be individually controlled.

User avatar
Quizatzhaderac
Posts: 1827
Joined: Sun Oct 19, 2008 5:28 pm UTC
Location: Space Florida

Re: Solving Lights Out

Postby Quizatzhaderac » Fri Jul 13, 2012 5:15 pm UTC

I'm guessing you want to make your own algorithm and not just take the light chasing one from Wikipedia?
The thing about recursion problems is that they tend to contain other recursion problems.

Giallo
Posts: 226
Joined: Sat Jan 01, 2011 11:31 pm UTC
Location: ETH, Zürich, Switzerland
Contact:

Re: Solving Lights Out

Postby Giallo » Fri Jul 13, 2012 8:39 pm UTC

Robert'); DROP TABLE *; wrote:
Giallo wrote:Well... 25 equations, 25 unknowns and (almost surely) the equations are linearly independent. I'd say that matlab/python/mathematica could help you ;)

I also tried this, but couldn't work out how to interpret the result. Asking Python to solve a grid of all lights being switched on yields a "solution" of

Code: Select all

[0.36, 0.32, 0.23, 0.32, 0.36]
[0.32, 0.23, 0.32, 0.36, 0.32]
[0.23, 0.32, 0.36, 0.32, 0.09]
[0.32, 0.36, 0.32, 0.09, 0.14]
[0.36, 0.32, 0.09, 0.14, 0.09]

(Rounded to 2 d.p.)
Since none of those are 1 or 0, I'm not precisely sure what they mean. (I can post the entire program I used to get that solution, if it's at all helpful.)


As Nitrodon pointed out, you have to work in Z/2Z, so you should at least implement a class for integers mod 2. Even then, I don't know if the classical solve in python would work, so you might have to implement some gaussian elimination or something similar (which would be really easy in this case...). I think I'll try it myself.
"Ich bin ein Teil von jener Kraft, die stets das Böse will und stets das Gute schafft."

User avatar
Snark
Posts: 425
Joined: Mon Feb 27, 2012 3:22 pm UTC

Re: Solving Lights Out

Postby Snark » Fri Jul 13, 2012 8:43 pm UTC

jaap wrote:Anyway, if you feel like delving deeper into the specifics of the maths behind Lights Out, have a look at my theory page.
That link is perfect. If you're not looking for anything besides 5x5 ordinary Lights Out, it would be very easy to program the solution that jaap's link shared. Great stuff!
Dashboard Confessional wrote:I want to give you whatever you need. What is it you need? Is it within me?


Avatar by Matt

User avatar
Robert'); DROP TABLE *;
Posts: 730
Joined: Mon Sep 08, 2008 6:46 pm UTC
Location: in ur fieldz

Re: Solving Lights Out

Postby Robert'); DROP TABLE *; » Sat Jul 14, 2012 4:33 pm UTC

Quizatzhaderac wrote:I'm guessing you want to make your own algorithm and not just take the light chasing one from Wikipedia?

I'm trying to solve a non-square version, which includes the variation that the light you click isn't toggled, which means the normal strategies don't work as easily. (But I'd also like a very general solver for the sake of it :P)

jaap wrote:Anyway, if you feel like delving deeper into the specifics of the maths behind Lights Out, have a look at my theory page.

I think I stumbled on that page a while back, but skipped over it because I thought it was telling me things I already knew. However, I looked more closely, and it really helped. I think the next step is to calculate the A-1 matrix, (which is annoying since I don't have any code on hand to do that) and multiplying that with the starting position should produce the solution.

I'll get back to you if I've got any problems once I've tried that.
...And that is how we know the Earth to be banana-shaped.

Giallo
Posts: 226
Joined: Sat Jan 01, 2011 11:31 pm UTC
Location: ETH, Zürich, Switzerland
Contact:

Re: Solving Lights Out

Postby Giallo » Sat Jul 14, 2012 4:59 pm UTC

Robert'); DROP TABLE *; wrote:I think the next step is to calculate the A-1 matrix


NEVER do that if you are solving systems of linear equations! It is much much faster to directly compute the solution with other methods (if I'm not wrong it's something like O(n2) vs. O(n3).

At least I've learned that much from the courses in numerical maths I've had to follow...
"Ich bin ein Teil von jener Kraft, die stets das Böse will und stets das Gute schafft."

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Solving Lights Out

Postby jaap » Sat Jul 14, 2012 9:57 pm UTC

Giallo wrote:
Robert'); DROP TABLE *; wrote:I think the next step is to calculate the A-1 matrix


NEVER do that if you are solving systems of linear equations! It is much much faster to directly compute the solution with other methods (if I'm not wrong it's something like O(n2) vs. O(n3).

At least I've learned that much from the courses in numerical maths I've had to follow...

It depends. If you have a particular lights out board and want to solve many different light patterns, then calculating A^-1 is the way to go. This is because the board fully determines A (and A^-1), and varying the light pattern you want to solve only varies the right hand side constant terms. Furthermore, calculating the inverse gives you all kinds of other information about the particular Lights Out board, such as the rank, null-space vectors (i.e. button patterns that have no effect), which lights can be individually switched, etc.

By the way, There is a neat Java applet on my site:
http://www.jaapsch.net/puzzles/lograph.htm
It allows you to draw any graph, and play lights out on its vertices. It has a built-in solver/analyser.

User avatar
PM 2Ring
Posts: 3715
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Sydney, Australia

Re: Solving Lights Out

Postby PM 2Ring » Mon Jul 16, 2012 7:04 am UTC

I'm not much of a gamer, and I'd never heard of Lights Out before this thread, but it reminds me of a classic old game I know as Flip. I posted a Python / GTK version of Flip in the coding forum a few years ago. I modified the code slightly last year (the buttons in the old version didn't display properly in my current main Linux distro (Mepis 11)). I just posted the improved version today: see Coding: Hacks and Snippets.

gorcee
Posts: 1501
Joined: Sun Jul 13, 2008 3:14 am UTC

Re: Solving Lights Out

Postby gorcee » Mon Jul 16, 2012 6:36 pm UTC

http://math.stackexchange.com/questions ... e-solution

This just popped up. Might be of interest.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 9 guests