Let's say I have a 3×3 "lights out" puzzle, where each light can have one of four states: 0, 1, 2, or 3. Tapping on each light adds 1 to its state and the state of all of the lights in its row and column. My goal is to get each light to the "0" state.
I've calculated the "neighborhood" matrix to be:
$$
\begin{matrix}
1 & 1 & 1 & 1 & 0 & 0 & 1 & 0 & 0 \\
1 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 \\
1 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \\
1 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 \\
0 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 0 \\
0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 1 \\
1 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 \\
0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\
0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 1 \\
\end{matrix}
$$
As I understand it, this matrix represents the behavior of tapping on a light that I described. That is, tapping on light 1 adds 1 to the state of lights 1, 2, 3, 4, and 7. Tapping on light 2 adds 1 to the state of lights 1, 2, 3, 5, and 8. etc…
Let's say I have a starting puzzle of:
$$
\begin{matrix}
2 & 3 & 1 \\
2 & 3 & 3 \\
2 & 2 & 2 \\
\end{matrix}
$$
I've been trying to solve this, but I'm missing something. My solutions keep turning out to be incorrect. Here's what I have been doing:
- Augment the neighborhood matrix with the puzzle state:
$$
\begin{matrix}
1 & 1 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 2 \\
1 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 3 \\
1 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 1 \\
1 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 2 \\
0 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 0 & 3 \\
0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 1 & 3 \\
1 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 2 \\
0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 1 & 2 \\
0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 1 & 2 \\
\end{matrix}
$$
- Calculate reduced row echelon form using gaussian elimination, keeping in mind the modulo 4 nature: $-1 = 3$, $-2 = 2$, $-3 = 1$, $5=1$, etc… Thus far I have calculated the reduced row echelon form to be:
$$
\begin{matrix}
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\
\end{matrix}
$$
This gives a solution of:
$$
\begin{matrix}
& 0 & 0 & 1 \\
& 1 & 1 & 0 \\
& 0 & 1 & 0 \\
\end{matrix}
$$
As I understand it, this solution means that I should tap lights 3, 4, 5, and 8 one time each. However, this solution seems to be incorrect, as performing these operations on the puzzle results in this state:
$$
\begin{matrix}
& 0 & 2 & 2 \\
& 0 & 2 & 2 \\
& 0 & 0 & 0 \\
\end{matrix}
$$
What am I doing wrong? What is the proper way to solve this sort of puzzle with these parameters?
Best Answer
The column you augment your neighbourhood matrix with needs to be the negative (mod $4$) of the puzzle state. The solution for your example is the negative of the one you've found—namely $$ \begin{matrix} 0&0&3\ \ \\ 3&3&0\ \ \\ 0&3&0\ \ , \end{matrix} $$ which worked when I tried it.