Many more Lights Out

 July 17, 2010 mathematics

\newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}}

\newenvironment{question}[1][]{\par\textbf{Question (#1).}}{} \newenvironment{theorem}[1][]{\par\textbf{Theorem (#1).}}{} \newenvironment{lemma}[1][]{\par\textbf{Lemma (#1).}}{} \newenvironment{proof}{\textit{Proof.}}{}

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