Turns out the algorithm is related to zero forcing sets. A fun concept. I found some nice slides on it. https://www.math.nsysu.edu.tw/~chlin/Publications/Slides/TUe2022.pdf
For a \(n\times n\) grid, the lights out game can be considered as solving a linear system over \(n^2\) variables in mod \(2\). It takes \(O(n^6)\) time. Surprisingly, there is a \(O(n^3)\) time algorithm. https://chaoxuprime.com/posts/2019-01-12-lights-out-game.html
I'm an Assistant Professor at the Algorithms and Logic Group in UESTC. I work on algorithms and combinatorial optimization.
The social network of the future: No ads, no corporate surveillance, ethical design, and decentralization! Own your data with Mastodon!