2022-05-01 19:36 UTC
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
Replies (2)
-
@chao@mathstodon.xyz 2022-05-04 17:33
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
-
@christianp@mathstodon.xyz 2022-05-02 05:38
@chao@mathstodon.xyz nice! So could the general idea be summed up as "solve the top row on its own, then work out what the row below would look like, and solve that too"?