Follow

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-

· · Web · 2 · 9 · 6

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

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

Sign in to participate in the conversation
Mathstodon

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