0
$\begingroup$

Let's say I have a 3x3 "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:

  1. 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} $$

  1. 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?

$\endgroup$
1
  • $\begingroup$ I’m not seeing the first line of your neighborhood matrix. $\endgroup$ Nov 3, 2019 at 21:46

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you! This was something I missed when I adapted the technique for solving modulo 2 lights out puzzles. $\endgroup$
    – aaryn101
    Nov 4, 2019 at 1:14

You must log in to answer this question.

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