Elektrine lite

← Feed

@chao@mathstodon.xyz

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

    Open ##5177146

  • @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"?

    Open ##5177147