Resolution of the game lights version
I am trying to create a decidability function for a game algorithm. Basically a function that returns true or false for a given game if it's resolvable or not.
Play is a type of game with lights. Basically you have a grid of M * N buttons. When the game starts, a random number or a saved pattern of these lights is turned 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.
source to share
The number of indicators in each row and each column must be even (where "0" is also considered "even").
Proof: Suppose you have to press 2 horizontal adjacent buttons. If you start with only 1 light, then at the far left, no matter what you do, you will get one light. On the other hand, once you have 2 lights at any distance, you can "move" one light close to each other until they land, at which point you can turn them off.
The same is true for vertically adjacent buttons and an extension for the 2x2 button grid: whenever you turn off any one light, the other switches ensure that the number of turns on remains a multiple of 2 per row and column.
This, for example, is solvable:
and it is not (note the odd numbers in some columns and rows):
source to share