Can some very clever person extend on what we already know and apply it to Lights Out 3D?
I tried briefly, but it seems a lot more complicated.
]]>Labelling the last line ABCDE, there are 5 different operations that you can do that affect nothing but the last line. These are BCE, ABC, ABDE, CDE and ACD.
Clearly, all of the board combinations can be reduced to one of the 32 boards that only involve the last line, and from there it's a question of which of those can be solved. Perhaps surprisingly, the only solvable boards other than the ones that are solved by just one of those operations are AE and BD (and of course, the one without any lights).
From there, a bit more poking around reveals that there are 3 sets of unsolvable boards such that each element can be transformed into another element in the set but no other.
Set 1:
{A, ABCE, ABD, ACDE, BC, BDE, CD, E}
Set 2:
{ABCD, ABE, AC, ADE, B, BCDE, CE, D}
Set 3:
{AB, ABCDE, ACE, AD, BCD, BE, C, DE}
Interestingly, each of those sets is just the solvable set but with A, B and C respectively added to each element.
A useful consequence of this is that if you get a randomly generated Lights Out board, then reducing it to one light on the edge of the board is proof that it can't be solved.
]]>But in your 2nd example above, you showed that there are distinct non-repeating combinations that change the board in the same way. So then, because the number of configurations is the same as the number of combinations, that must mean that there are some boards that can't be solved. I'd always assumed the opposite.
]]>Pressing matrices would then thus the fundamental building blocks of the game of Lights Out. It would mean that starting with the zero matrix (the board with all lights off), we could arrive at any arbitrary board configuration by executing a finite series of presses which would mean (working in reverse) that every board setup in Lights Out can be solved.
PS: In the 5×5 case, there are only 25 pressing matrices. Therefore the number of finite combinations of distinct pressing matrices is only finite. It should thus be straightforward to check if between them they yield all the 2[sup]25[/sup] possible board configurations you just need a good program, or a lot of time on your hand.
]]>where + is matrix addition. And Theorem 3 proves the other two theorems! Theorem 1 is proved by the fact that matrix addition is commutative and associative, while Theorem 2 is proved by the fact that since the matrices in
are over a two-element field, L + L = 0 for all L ∈ .]]>Thus, using this simpler notation, my first board above can be represented by the matrix
and the second board above by
The two statements in my first post can thus be formally stated as theorems.
Theorem 1:
(NB: Ive stated the theorem for only two multipliers; mathematical induction should see to it that it works for any finite number of multipliers.)
Theorem 2:
So now that we know that it's possible to have solutions that aren't contained in each other, the next logical question would be whether or not you can have more than one optimal solution.
]]>Short solution: Press #3 #11 #15 #23 (i.e. the midpoints of the edges of the grid)
Long solution: Press all the even-numbered lights
Again neither solution involves pressing a light more than once. This time, however, neither solution is contained in the other! This makes the example wholly non-trivial.
Heres the proof of why the long solution works. Since the even-numbered lights are all either at least two lights apart or diagonally separated, pressing an even-numbered light has no effect on any even-numbered light other than itself. Of the odd-numbered lights, only the ones at the midpoints of the grid edges are adjacent to an odd number of even-numbered lights. All the other odd-numbered lights are adjacent to an even number of even-numbered lights. Hence pressing all the even-numbered lights will change the state all the even-numbered lights plus #3, #11, #15 and #23, and leave the state of all the other lights unchanged in other words, it should turn off all the lights above.
]]>That's an interesting point actually. Can Lights Out boards have more than one solution that doesn't involve pressing a light twice?
Yes indeedy, they can. Consider the following setup:
You can do it the short way by pressing the four corner lights. Or you can do it the long way by pressing all the lights on the edge plus the second-from-left, second-from-right, second-from-top and second-from-bottom middle lights. Neither solution involves pressing a light more than once. If you dont believe it, you can try it yourself here: http://www.guzer.com/games/switchit.php
PS: There is a very interesting corollary to the above. Notice that the short solution is actually contained in the long solution. This means that if the lights are numbered #1#25 left to right from top to bottom, then pressing the following lights (in any order) will leave the entire board unchanged: #2 #3 #4 #6 #8 #10 #11 #12 #14 #15 #16 #18 #20 #22 #23 #24. (Thats all the even-numbered lights plus the midpoints of the four edges of the grid.)
]]>The wikipedia page gives a very sloppy way of solving a board.
Basically, eliminate all rows except the bottom one by pressing all lights directly below 'on' lights and working your way downwards. Then look at a table and press buttons according to what lights are left on in that row.
The worst part is that even then you may not be done, and you'd have to repeat the process until you finished. It's very possible that you might take a far higher number of moves that you need to. But to improve it, you'd just write down all the moves of the 'bad' solution, cross out repeating squares in pairs, and there you have a better solution. Possibly still not the best one, but certainly an improvement.
That's an interesting point actually. Can Lights Out boards have more than one solution that doesn't involve pressing a light twice?
]]>Pressing (m,n) toggles the following lights: (m,n), (m+1,n), (m,n+1), (m−1,n), (m,n−1)
Pressing (m+1,n) toggles the following lights: (m,n), (m+1,n), (m+2,n), (m+1,n+1), (m+1,n−1)
Finally pressing (m,n) again toggles the same first five lights.
The upshot of all this is that 8 different lights have been toggled. Of these, (m,n+1), (m−1,n) and (m,n−1) have been toggled exactly twice, so there is no change in their state. Of the others, (m,n) and (m+1,n) have been toggled exactly three times while the rest have been toggled exactly once so these have changed state.
In other words, the lights that have changed state are (m,n), (m+1,n), (m+2,n), (m+1,n+1), (m+1,n−1) which are precisely those lights that would be toggled by pressing just the adjacent light (m+1,n) alone.
]]>Note that pressing a light twice is equivalent to not pressing it at all (indeed pressing a light an even number of times is equivalent to not touching it while pressing it an odd number of times is equivalent to doing so just once).
I don't think this is so. Pressing a light, then an adjacent light, then that light again will change the puzzle. So it is not the equivalent of just pressing it twice in a row.
]]>