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
@chao 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"?
@christianp but to solve the top row on its own, we have to work out what the rows below look like 😂. So this is a 3 step process: 1. Express all the rows below as linear combination of the first row. 2. Use the system of linear equations for the last row to solve for the first row. 3. Use the first row to work out the rest of the rows. (updated the original blog post to make this more clear)
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