solvability of a version of lights out game [duplicate]

Question

I am trying to create a solvability function for a game algorithm. Basically a function that returns true or false for a given game if it is solvable or not.

The game is a type of lights-out game. Basically You have a M*N grid of buttons. When the game starts, a random number or a stored pattern of these lights is switched on. Pressing any of the lights will toggle a square of four buttons including the pressed button.

so I'm looking for an algorithm that returns true if we can turn off all the lights and return false if we can't do this.

Semifluid

"A square of four including the pressed button" -- are there other constraints? For a button not on an edge, there are four possible 'squares of 4'. – Metternich

there are no other constraints and there is no different between these four possible squares of 4. – Semifluid

I don't get it. How is decided which square of 4 gets toggled, relative to the pressed button? – Metternich

Let's say in this way that we have a big hand and in each step we press a square of 4 buttons together instead of one. – Semifluid

Or, in each step we choose a square of four buttons and toggle the states of it's buttons – Semifluid

Okay--apologies for misunderstanding. One always presses a square of four buttons (rather than "one with 3 around it). I think you can brute-force test it by having the computer always press (x,y),(x+1,y),and the row below it, for every lighted button (x,y). If you end up with a light at the very right or bottom, it can't be done. – Metternich

The game in the duplicate seems different; it toggles neighbouring lights, not any 4x4 square. – Metternich

@Jongware: The answers given to that question will work regardless of which lamps each button toggles, though. Still, your answer gives a simple solvability criterion for this particular instance of the game that doesn't apply to more general variants, so I do agree that it's worth keeping them separate. – Weinstein

This is not a duplicate. It is fundamentally different from the cross-style lights-out puzzle in terms of parity checking, and it also concerns itself with "is it solvable?" rather than "how to solve it" – Carmine

Answer 1

The number of on-lights in each row and each column must be even (where '0' is considered 'even' as well).

Proof: suppose you must press 2 horizontal adjacent buttons. If you start out with 1 light only, at the far left, no matter what you do, you will end up with a single light on. On the other hand, as soon as you have 2 lights at any distance, you can 'move' one light close to the other until they are adjacent, at which point you can switch them both off.

The same is true for vertically adjacent buttons, and by extension for a 2x2 button grid: whenever you switch off any single certain light, the other toggles ensure the number of on-lights stays a multiple of 2 per row and column.

This, for example, is solvable:

and this one is not (note the odd numbers in some columns and rows):

Metternich

+1. Your answer could be even better, though, if you also proved this solvability criterion to be sufficient as well as necessary (i.e. that the methodical solution method demonstrated in your animations really does solve all boards satisfying the criterion). – Weinstein

@Ilmari: I briefly considered that ... but my maths is not sufficient to extend it! I tried a number of totally random boards and could not find a counter-example, so at least my logic holds heuristically. – Metternich

@Metternich What did you use to create these gifs? – Kirin

How does this solvability test apply to a classic 5x5 board? (BTW, I wonder why you haven't take that as en exampl but a much more complated case and in fact with size ...) – Endomorphic