# Puzzle identification and solving algorithm

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.

-
Is the only move by the player to choose two buttons and push them simultaneously? Otherwise you can push all the buttons and win in one move. What is 8x8 in this puzzle? Can you tell us anything else? A puzzle of this kind need not have a solution. –  Samuel May 16 '13 at 20:24
Samuel, thanks for feedback. I've edited my post. Please ask if you need more information. Also, solution exists, I've been told by author and I managed to solve it with try-error method. –  n00b May 16 '13 at 20:35
How are the buttons numbered? what does 25, 36, etc. mean? –  vadim123 May 16 '13 at 20:36
vadim123, I cleaned up the question, please check above. 25 means button number 25. –  n00b May 16 '13 at 20:45
Clicking on 25 turns button 2 on, but shouldn't then clicking on button 55 turn button 2 off again? –  Samuel May 16 '13 at 20:52

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.

-
Thanks alex.jordan! Can you please give me little bit more instructions for next step thru example? It's been a long time since I've done any math :( –  n00b May 16 '13 at 21:48
alex.jordan, btw, what do you think that I'll ever push some button 0 or 1 time? –  n00b May 16 '13 at 22:17
Also, how could I determine in which order I should press buttons? –  n00b May 16 '13 at 22:26
@noob I added a $2\times2$ example. Also, you should understand that order is irrelevant. Whether we push button A, then button B or vice versa, the net effect is the same. –  alex.jordan May 16 '13 at 23:08
Ok. I wrote 64 equations with your instructions and converted it into matrix and run row reduction echelon form on them. Here is the defined matrix and row reduction echelon form result for this set: pastebin.com/raw.php?i=3wMFbBca. Please save as txt file and open in notepad so it doesn't break correct newlines. How can I proceed? –  n00b May 17 '13 at 19:57