Puzzle identification and solving algorithm

Question

I am trying to solve 8x8 puzzle (total 64 buttons). Similar to LightsOut, but in this rules are different. Goal is turn ON every button.

Example:

Button 1 is turned on/off by buttons 25, 36
Button 2 is turned on/off by buttons 25, 55
Button 3 is turned on/off by buttons 20, 58
...
Button 20 is turned on/off by buttons 4, 9
...
Button 25 is turned on/off by buttons 22, 59
...
Button 36 is turned on/off by buttons 42, 50
...
Button 55 is turned on/off by buttons 3, 24
...
Button 64 is turned on/off by buttons 29, 32

Full list is available here: http://pastebin.com/9b0MKXCb

I see that every button can be turned ON/OFF by any of 2 buttons (it's always 2).

I succeeded solving it manually by trial & error method, but I would like to do it proper. Program starts with all lights (buttons) turned OFF. Target is to turn ON all of them.

Is this still LightOuts problem? How can I solve it?

Thank you!

UPDATE:

I've been asked why is this 8x8 puzzle. I called it that because there is total 64 buttons. Is this wrong?

For example. If I wish to turn ON button 1, I have to click on button 25 or 36. If I click two times on 25 or 36 state is restored - it's like nothing happened.

So if I wish to turn ON buttons 1 and 2 I have to click on button 25 OR button 36 AND button 55.

Answer 1

Let $x_i$ be the number of times you push button $i$. You'll only ever push it $0$ times or $1$ time, so be can take $x_i$ to be modulo $2$.

You would like light 1 to go from OFF to ON. When we examine the chart in the link in your comments, we can only affect light 1 by switching buttons 25 or 36. This yields an equation: $$x_{25}+x_{36}\equiv1$$ so that light 1 will be left ON. Repeat this for every light, and you have 64 equations modulo $2$ in $64$ variables modulo $2$. This system of equations can be solved through row reduction of the corresponding matrix (or possibly row reduction will reveal there is no solution.) If there is a solution, it is either

• a specific set of values of 0s and 1s for the $\{x_i\}$,
• or it is a larger solution set that maybe parametrized, from which you can find an optimal specific solution my minimizing (the integer value of) $x_1+x_2+\cdots+x_{64}$.

---

Let's take a smaller, $2\times2$ example. Mimicking the link you provide:

1 = [2,4] (button 1 triggers state change on button 2 AND button 4) 2 = [1, 3] (button 2 triggers state change on button 1 AND button 3) 3 = [1, 2, 4] (button 3 triggers state change on button 1, button 2, AND button 3) 4 = [3]

$$\begin{align} \text{To turn on light 1} &&x_2+x_3&=1\\ \text{To turn on light 2} &&x_1+x_3&=1\\ \text{To turn on light 3} &&x_2+x_4&=1\\ \text{To turn on light 4} &&x_1+x_3&=1\\ \end{align} $$

This system of equations has matrix $$\begin{align}\begin{bmatrix} 0&1&1&0&1\\ 1&0&1&0&1\\ 0&1&0&1&1\\ 1&0&1&0&1 \end{bmatrix}\end{align}$$ Row reducing (if you do not know how to do this, please research it online - wikipedia should do) yields: $$\begin{align}\begin{bmatrix} 1&0&0&1&1\\ 0&1&0&1&1\\ 0&0&1&1&0\\ 0&0&0&0&0 \end{bmatrix}\end{align}$$

$x_4$ is a free variable, so we can use a parameter $t$ for $x_4$. $t$ can range between $0$ and $1$. For the rest, we read (using modulo 2 arithmetic) $x_1=1-t, x_2=1-t, x_3=t$. This yields two solutions. $t=0\implies(1,1,0,0)$ and $t=1\implies(0,0,1,1)$.

So we could either push buttons 1 and 2, or buttons 3 and 4. the order that we push them in is irrelevant.