Turns out the algorithm is related to zero forcing sets. A fun concept. I found some nice slides on it. math.nsysu.edu.tw/~chlin/Publi

Show thread

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. chaoxuprime.com/posts/2019-01-


The social network of the future: No ads, no corporate surveillance, ethical design, and decentralization! Own your data with Mastodon!