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-

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

· · Web · · ·

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