Mini Lights Out

There are several variants of Merlin's Magic Square puzzle. It is called "Mini Lights Out" to distinguish it from the 5×5 puzzle, which we'll present elsewhere. The one below is played on a 4×4 board wrapped on a torus. That is, the uppermost and lowermost rows are considered neighbors and likewise the leftmost and rightmost columns are considered neighbors. The task is to switch all the buttons off. Each button is embedded into a neighborhood of five buttons according to the 4-connectedness rules. A button's neighborhood includes the button itself and its vertical and horizontal neighbors. All neighborhoods on the torus consist of five buttons. When a button is pressed, all the buttons in its neighborhood are affected and change their states.

The Theory

Copyright © 1996-2008 Alexander Bogomolny

As in Merlin's Magic Square, we use linear algebra to represent the problem. Given an ordering of the buttons, a configuration of buttons is associated with a 16-vector v = (v₁ v₂ ... v₁₆)^T, where v_i = 1 if the i^th button is lit and v_i = 0, otherwise. 16-vectors are also used to describe a strategy, or a sequence of button presses. s = (s₁ s₂ ... s₁₆)^T, where s_i = 1 if the i^th button is pressed and s_i = 0, otherwise. Clearly it is never needed to press the same button twice as two button presses cancel each other's effects. The ordering of the presses is also inessential.

Applying a strategy s to an originally unlit board is equivalent to multiplying a certain 16×16 matrix A by s. The vector As shows the resulting configuration. Also, due to the binary nature of the setup, the strategy for turning off a given set of lights is identical to the strategy for turning those same lights on from an unlit board. Therefore, given an initial configuration v, our goal is to find a strategy vector s so that As = v (mod 2).

Note that if s has a single 1 with the rest being 0, As has 1s corresponding to the neighborhood of the associated button. (This is actually the definition of the matrix A.) As a matter of fact that can be checked experimentally, if s has 1s in the neighborhood of a button with 0s elsewhere, As has a single 1 corresponding to this button. The algebraic implications of this is that As = v is equivalent to s = Av, or A² = I, the identity matrix. This also means that the problem has a unique solution (strategy) Av for any starting configuration v.

We note that because of the specific size of this puzzle, the neighborhoods of two distinct buttons will always intersect in either 0 or 2 buttons. We now give the following

Definition

1. Two buttons are said to be disjoint if their neighborhoods are disjoint.
2. The count of a button is the number of buttons in its neighborhood that are currently turned on.
3. The parity of a button is the parity of its count.

Suppose a button has a current count of n. Pressing that button will change its count to 5 - n, and thus change its parity. Pressing a disjoint button will not change the original button's count or its parity. Pressing a non-disjoint button will make the original button's count either n + 2, n - 2, or n, depending on whether the buttons common to both neighborhoods were, respectively, originally both off, both on, or one on and one off. Thus the original button's parity will not be changed by pressing a non-disjoint button. This leads to the following

Theorem 1

Combining Theorem 1 and the fact that every starting configuration is solvable, we get an easily implemented method to solve the Mini Lights Out game. Clearly, at the end of the game each button must have parity 0. By Theorem 1, this parity can only be changed by pressing that button. Thus we merely press those buttons whose parity is one.

References

1. J. Missigman, R. Weida, An Easy Solution to Mini Lights Out, Mathematics Magazine, Vol. 74, No. 1. (Feb., 2001), pp. 57-59.

Copyright © 1996-2008 Alexander Bogomolny