2
$\begingroup$

There is a $5 \times 5$ square of lights, of which some number are on and off. "Selecting" a light changes the state of the selected light and all four lights adjacent to it, in effect, changing the state of the lights in a plus centered on the selected light. The ultimate goal is to have every light in the puzzle in its "off" state. Is there a surefire algorithm to solve this using something like a binary matrix? If no, what is the most efficient method to solve this puzzle with only one light on, in the center?

$\endgroup$
1
  • $\begingroup$ See this solution of the same problem i stated before, also the one proposed by gamo is of worth for anyone who can understand logical proofs. $\endgroup$
    – Abr001am
    Commented Mar 19, 2018 at 14:19

1 Answer 1

4
$\begingroup$

Represent a configuration as a $25$-dimensional vector over $\mathbb{F}_2$, the field with two elements. Each component of the vector corresponds to one of the lights. $1$ represents on, and $0$ represents off.

You can also represent a sequence of moves as a $25$-dimensional vector over $\mathbb{F}_2$ because of two properties:

  1. Toggling a light twice has the same effect as not toggling it at all.
  2. Toggling a set of lights in any order has the same effect.

So the component corresponding to a certain light represents the number times you select it $\pmod{2}$.

Now, let $A$ be the adjacency matrix of the $5\times 5$ rectangular grid graph with $1$'s in the diagonal. Let $\vec{x}$ be the unknown solution to a given initial configuration $\vec{b}$. Then you need to solve the system of $25$ equations $\vec{b}+A\vec{x}=\vec{0}$ which is equivalent to $A\vec{x}=\vec{b}$ over $\mathbb{F}_2$. In your specific problem, you need to set $\vec{b}$ to the vector where the component corresponding to the light in the center is a $1$ and the rest are $0$'s. Solve the system of equations. You may get no solution, a unique solution, or many solutions. If you get many solutions, compare each of the solutions directly to figure out which solution involves pressing the fewest lights.

It so happens that there are $4$ solutions to your problem, and they are all equivalent to each other by rotation. Here's one of these $4$ equally optimal solutions, which toggles $11$ lights: $$\begin{matrix}1&1&0&0&0\\0&0&1&0&0\\1&0&1&1&0\\1&0&0&0&1\\0&1&1&0&1\end{matrix}$$

P.S. I've actually been studying the mathematics of Lights Out for a few years. The topic fascinates me and I'm trying to publish a paper about fractal patterns in the solutions to larger boards of size $2^n\times 2^n$. There are many different classes of board sizes whose solutions give fractal patterns, and my profile picture is the pattern that emerges from boards of size $7(2^n)-1\times 7(2^n)-1$.

$\endgroup$
4
  • $\begingroup$ Do you have any papers published on this yet? I'm a highschooler studying the Lights Out puzzle for research, and I actually recognized your profile picture in some of my studies. Specifically, it has the same fundamental fractal nature of my solution set to toggling a single light on the infinite lights out board. $\endgroup$ Commented Jun 25, 2018 at 3:24
  • $\begingroup$ @greenturtle3141 My paper is still being reviewed by the journal I submitted it to. And your reason for recognizing my profile picture is accurate. I believe the solution you mention on an infinite board is the limit of the "mikado diamonds", mentioned in Note on the Lamp Lighting Problem. I show the relation between mikado diamonds and solutions to $2^n\times 2^n$ boards in my paper. $\endgroup$
    – Riley
    Commented Jun 25, 2018 at 3:40
  • $\begingroup$ Dang, it kinda sucks to find out I'm not original. Any suggestions for finding new directions of research? $\endgroup$ Commented Jun 25, 2018 at 5:14
  • $\begingroup$ @greenturtle3141 Just keep exploring new things. Don't be discouraged if you can't find anything original. Look at others' work as an opportunity to learn. $\endgroup$
    – Riley
    Commented Jun 25, 2018 at 5:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .