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 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)
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!