Many more Lights Out

 2010-07-17 00:05:32 +0000 mathematics

A very long while ago I posted some solutions to Lights Out; back then, I solved the $n$-by-$n$ board by row-reducing an $n^2$-by-$n^2$ matrix.

Since then, both Boris Okun and Brent Werness pointed out to me that I should've solved Lights Out by using a scanning algorithm: propagating the button presses down one row at a time, and exponentiating the propagation matrix to make sure that I don't get stuck at the last row.

This is much faster.

With this method, here is a (scaled down, auto-leveled) 2000-by-2000 solution:

Solution to 2000x2000 Lights Out

And here is a (very much scaled-down, auto-leveled) 5000-by-5000 solution:

Solution to 5000x5000 Lights Out