3
$\begingroup$

Recently in World of Warcraft, there is a puzzle that is very similar to the "lights out" puzzle where a player needs to flip switches to turn all the lights into a specific color (in this case yellow, green, red, white). I have seen other solution to the lights out problem using linear algebra however all these uses only 2 states (on or off).

I haven't ever ran into a system of linear equation with modular operation before and would like some help solving something like:

  L_1 = ((s_1 + s_2 + ...s_n + c_1 ) mod 4)

  L_2 = ((s_1 + s_2 + ...s_n + c_2 ) mod 4)

           ...

  L_n = ((s_1 + s_2 + ...s_n + c_n ) mod 4)

where each L has some linear combination of s + constant mod 4

$\endgroup$
  • $\begingroup$ It will be a bit different mod 4 because 2 doesn't have a modular inverse, so mod 4 doesn't form a field. But you can still do gaussian elimination on the matrix, just do all the adding and mulitplying mod 4 and try hard to pick odd numbers to make into pivots. $\endgroup$ – DanielV Dec 17 '18 at 1:27
  • $\begingroup$ See the 2017 article "Lights Out" and Variants by Martin Kreh in the American Mathematical Monthly which specifically treats modular colors on square grids. $\endgroup$ – Brian Hopkins Dec 17 '18 at 3:21
2
$\begingroup$

You can solve the mod 4 version like two instances of the mod 2 version.

First treat states $1$ and $3$ as if they are switched-on lights, and states $0$ and $2$ as if they are switched-off lights. Solve this as the normal lights out. You are essentially just working mod $2$, making everything even. At the end of this stage, all lights are either $0$ or $2$.

Then solve the rest as another two-state lights out puzzle, where $2$ is the switched-on state and $0$ is a switched-off state. The only difference is that the moves you do consist of double button presses. A double button press skips over the $1$ and $3$ states, and toggles lights between the $0$ and $2$ state.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.