Strategy for Modified Lights out

Question

A friend of mine showed me a variation of lights out that they were interested in, and asked me if it would be possible to solve any given empty grid. This variation involves toggling not just the immediate neighbours, but all cells that are in the same horizontal row or vertical column, such that the cells that are toggled form a cross. See the picture below:

At the time, I was unaware that all lights out variations were able to be solved, but I was still able to prove that all empty grids could be solved such that all lights are toggled on. The question is, what strategy/strategies could you come up with to optimally solve any fully empty grid? Also, if you're up to it, what strategy/strategies could you use to solve a grid that has been legally scrambled?

Answer 1

This game is a version of Lights Out. Like all these games, they have the following properties:

• The order of moves does not matter. If you look at the effect of a move sequence on a single square, all that matters to that square is how often it is toggled. It does not matter to that square what order the moves are performed, as all the moves that affect it will affect it in the same way.

• Each square need not be tapped more than once. If you were to tap a square more than once during a solution, you can reorder the moves to make those two taps consecutive. But tapping a square twice has no net effect, so such repeated moves can be skipped.

This means that there are only $2^{a*b}$ possible move sequences that need to be considered on an $a$ by $b$ board - each square can either be tapped or not by the move sequence.

Boards with only even dimensions

Consider now an ideal situation in which it is possible by some sequence of taps to change the state of just a single square without affecting the rest.

By rearranging the rows and columns of that sequence of taps, any single square can be changed. Therefore every state combination can be achieved from the all-off state.

In this ideal situation, all $2^{a*b}$ state patterns can be achieved. Since there are only $2^{a*b}$ move sequences, every combination of states has a unique solution.

For $a\times b$ boards with both $a$ and $b$ even, we are in this ideal situation, because tapping a square together with all the squares in the same row and those in the same column changes only that single square (it toggles $a+b-1$ times, the column toggles $a$ times, the row $b$ times, the rest $2$ times).

We know that tapping every square will change the all-off state to all-on (everything toggles $a+b-1$ times) and from the above we know that this is the unique solution so $a*b$ moves are necessary. It cannot be done more optimally.

Boards with odd dimensions

If $b$ (the length of a row) is odd and $a$ even, then we are not in this ideal situation. This is easy to see because pressing the squares of a single row toggles everything. So we can get from all-off to all-on by pressing either the first row, or the second row, etc. This pattern clearly does not have a unique solution.

In general this can allow for shorter solutions to those patterns that can be achieved. Because tapping all the squares of any two rows will have no effect on the state, any move sequence that uses more than $a$ taps on a pair of rows can be shortened - just exchange the tapped squares for the untapped ones on those rows.

However, for changing the state of all lights, the most optimal solution is just pressing all the lights in a single row. This is obvious when $a<b$, but not obvious in general. I'm not sure if there is an easy proof. I think the only way is to establish what the linear dependencies are, to show that the only patterns that have no effect on the lights are those where all the squares in an even number of rows are pressed. This shows that the solution where a single row is pressed cannot be reduced any further.

Of course the same reasoning applies if $a$ is odd (the height of the columns) and $b$ even, in which case the optimal solution for changing every light is to press a single column.

If both $a$ and $b$ are odd, the most optimal is to press a single row or a single column, whichever is shortest.

Answer 2

The least-thinking-required solution for the example grid is

Toggle every square.

This works for any empty square grid, and also

any grid where the width and height are both even, or both odd. In either case, every square has an even number of ”neighbours”.

For the remaining case of

odd x even, toggle everything in one column (or row), choosing the direction so that odd number of squares are toggled. Come to think of it, this also works for the odd x odd case, and is optimal as long as you choose the shorter direction.

Answer 3

I'm actually writing my (high school) research paper on this. Here are my conventions:

• We are trying to turn the lights off.
• Buttons and lights refer to the same physical object. However, we refer to the thing as a buttons in the context of pressing it, and as a light in the context of a toggle in state (We press the button to toggle the light).
• Two lights are neighbors if pressing one's button will toggle the other (In your variation, two lights are neighbors if they lie in the same row or column). By convention, we let a light be a neighbor of itself.
• Denote an easy-run as the action of pressing all on buttons at once (I believe Bruce Torrence came up with this term).
• We let an initial configuration of lights be easy if you can win with one easy-run.
• We let an initial configuration of lights be easy-iterable if you can win with several easy-runs.

I prove that in the two-state alien tiles variation,

• Boards with dimension $2n \times 2n$ are always solvable.
• Boards with dimension $2n \times 2n$ are always easy-iterable (In at most two easy runs) for any initial configuration.
• Boards with dimension $2n+1 \times 2n+1$ are easy for any solvable initial configuration.

It's really easy to prove that boards of even dimension are always solvable. It suffices to show that you can toggle any individual light. To do this, just press all buttons in that light's row and column. Some basic parity analysis will show that this always works (keep in mind that the dimensions are even).

Unfortunately, this is not the same for boards of odd dimensions (Ignore the $1 \times 1$ exception). For those who are not familiar with Lights Out analysis, here is how we can make this argument: If there are $N$ buttons, then there are $2^N$ possible initial configurations of lights (legal or not). There are also $2^N$ possible solutions (ways to press the buttons. Just like how a light can be on or off in an initial configuration, a button is either pressed or not pressed in a solution).

If we claim that all initial boards must be solvable, then for each of the $2^N$ possible initial boards, there is a solution. But there's also $2^N$ solutions, so there is a bijection between initial boards and solution.

Now take an empty board of odd dimensions. A solution to this board is to press nothing. If we find another solution, then there is no bijection between initial boards and solutions, so this would prove that not all initial configurations are solvable.

There are actually many other solutions. Just pick two rows, two columns, or a row and a column minus their intersection, and press all buttons in there. It's easy to show that this will still result in an empty board.

But that's not very interesting. I think the most interesting result here is that you can win with just easy-runs. For the odd-dimension case, you only need one easy-run, and you win. So, winning is a pretty mindless process (though, note that this solution is not necessarily optimal). For the even-dimension case, you need at most two-easy runs, which is not as mindless, but still really easy to execute. So unless you are trying to be optimal, this observation absolutely kills the difficulty of this variation. Let's prove that the killing actually works.

The odd-dimensions case is really easy. I used induction. Here is a brief sketch: In the inductive step, we can traverse through all legal configurations of lights by pressing any button. Basically, given an initial configuration that we know is easy, we just prove that after we press a button, the configuration is still easy. We can use the obvious all-off board as our base case. The meat of the proof is not hard: Just use the fact that an initial configuration is easy if each light that is on has an odd number of neighbors that are also on, and each light that is off has an even number of neighbors that are on. I leave the details to the reader.

The even-dimensions case is tougher. To reword the desired: We want to prove that after an easy-run, we get an easy game. I leave the bulk of this proof to the reader. Here is a rough sketch:

1. Prove this lemma: Consider some initial configuration of lights, and let $X$ be the set of lights toggled when all lights that are on are pressed. Then $X$ is the unique set of buttons to press that solve the board.
2. Prove this lemma: All solution buttons have an odd number of neighbors that are on, and the rest of the buttons have an even number of neighbors that are on. (A solution button is a button that needs to be pressed in the unique solution).
3. Case bash on the four types of lights arising from the properties of on/off and solution button/not a solution button.

In case you are wondering whether or not I actually did these proofs, here is an excerpt from my not-final-draft paper: https://www.dropbox.com/s/e312cri57z4egap/deleted_Lights_Out.pdf?dl=0

(I am a high school student that is bad at writing, pls dun judge)

So yeah, this Lights Out variation is pretty dead. Dead in a really cool way, though.

Jaap S made a pretty Lights Out variation game, so you can test out the easy-runs here: https://www.jaapsch.net/puzzles/javascript/lightjvr.htm

(To make the Alien Tiles thing, check both wrap-around boxes, and be a bit careful with the move-shape: If the board is $4 \times 4$, don't make the move shape the biggest cross possible, because some buttons might be pressed twice per move)