Lights Out on graphs (Q2088176)

The authors in this paper provide several variants to the classical ``lights out problems'' which seek on a \(5\times 5\) grid of lights where they also function as switches concurrently. Here touching a light will toggle the state of this light and its adjacent neighbors between off and on. So when a random set of lights are on, then the aim is to turn all lights off, if possible with a minimum number of operations. That is, a given initial state has to be transformed into a prescribed final state. Relying on a version of the Fredholm alternative, the authors introduce a separating invariant of the game and several of its variants, that is when an initial state can be transformed into a final state if and only if the values of the invariant of both states agree. They propose several variants of it, where the analysis relies on systems of linear equations over the ring \(\mathbb{Z}_n\). Although it is easy to find a concrete solution to the Lights Out problem, they show that it is NP-hard to find a minimal solution.