Lights Out illustrates many interesting mathematical concepts
including group theory and linear algebra. The game can change state
with simple operations which involve clicking on one of the lights.
In fact the game behaves as a mathematical group whose states
are closed under this operation. Even more, the game is an example of
an Abelian group meaning that operations are commutative. For
example if you start with a board in position X, click lights a
and then b, you will get the same result by clicking b
and then a. Thus if position X is made from position Y with moves
a1, a2, ..., an, then it does
not matter what order you make those moves; you will still end up at Y.
It is also true in Lights Out that if you press a button and then
press it again, the net result is that nothing changed. As a result,
in a set of moves a1, a2, ...,
an, there is no reason to have any ai =
aj because they would just cancel each other.
It is now feasible to consider a function of an input meaning what
would be created from an empty board by pressing a certain sequence of
buttons. Then for example,
(.....) (.X...)
(.X...) (XXX..)
f (.....) = (.X...)
(.....) (.....)
(.....) (.....)
The example shows one pressing a single button near the upper left
corner, and what the result would be. (An 'X' signals a light is on
and a '.' means the light is off.) Since we have defined the
function, now let us consider some of its properties:
An identity "0" exists which is the empty board.
X + 0 = X (the + operation is the bitwise XOR function)
X + X = 0 (anything XORed with itself is zero)
f(X + Y) = f(X) + f(Y)
if X is symmetric about some axis S, then f(X) is also symmetric
about S.
The object of Lights Out is now to find an inverse of this function,
meaning that given a board X, we wish to find the set of inputs Y such
that f(Y) = X. However, we still do not know yet if this inverse function
actually exists. Is the mapping made by f unique? Does there exist
two different inputs X and Y such that f(X) = f(Y)? In fact, the
answer is that it is not unique. Since level 1 was easy, we will use
it as an example. Two different solutions to level 1 are illustrated by
(..X..) (X...X) (.XXX.)
(.....) (X.X.X) (X.X.X)
f (X...X) = f (X...X) = (XXXXX)
(.....) (X.X.X) (X.X.X)
(..X..) (X...X) (.XXX.)
What we are interested in now, is how many solutions are there to
f(X) = 0? It is clear that f(0) = 0, but are there other solutions?
There are actually four solutions which are:
(.....) (X.X.X) (XX.XX) (.XXX.)
(.....) (X.X.X) (.....) (X.X.X)
(.....), (.....), (XX.XX), and (XX.XX)
(.....) (X.X.X) (.....) (X.X.X)
(.....) (X.X.X) (XX.XX) (.XXX.)
These four solutions form the nullspace of f. Call these
solutions S1, S2, S3, and
S4. S1 is obviously a solution to f(X) = 0, but
the others are not as obvious. In fact, S4 just equals
S2 + S3, since f(S4) =
f(S2 + S3) = f(S2) + f(S3)
= 0 + 0 = 0.
The idea of the nullspace is an important one and much can be derived
from it. If f(Y) = X, then f(Y+S1) = f(Y+S2) =
f(Y+S3) = f(Y+S4) = X, and hence every board X
has four different solutions. The solutions may have different
numbers of moves so the optimal solution is the one with the fewest
moves.
The nullspace has another important application. There are
2 ^ 25 possible input boards in the domain because there are
25 positions each of which can be on or off. Since the mapping done
by f is four to one, then the range has 2 ^ 23 boards. Thus
there are only 2 ^ 23 solvable boards. Since there are also
2 ^ 25 total boards then only one quarter of them are actually
solvable, and all of those solvable boards has four solutions. If you
tried level 25 in the game, you would never be able to win since it is
actually one of those boards not in the range of f.
The Solution
One of the solutions to Lights Out is a simple algorithm. The
algorithm involves making the board so that all of its lights are on
the bottom and then solving positions containing lights only on the
bottom row. The are 32 possibilities, but only 8 are solvable.
It is easy to push all the lights to the bottom row. Whenever there
are lighted squares above the bottom row, find one closest to the top, and
click on the square directly below that light. Taking level
1 as an example:
(.XXX.) (.....) (.....) (.....) (.....)
(X.X.X) (.XXX.) (.....) (.....) (.....)
(XX.XX) ==> push (.....) makes (X.X.X) ==> push (.....) makes (.....)
(X.X.X) (.....) (X.X.X) (X.X.X) (.....)
(.XXX.) (.....) (.XXX.) (.....) (XX.XX)
From this calculation, we can derive
(.....) (.....) (.XXX.)
(.XXX.) (.....) (X.X.X)
f (.....) + (.....) = (XX.XX)
(X.X.X) (.....) (X.X.X)
(.....) (XX.XX) (.XXX.)
{P}
Let P be the partial solution. Now all the lights are on the bottom
row. By knowing three functions
(.X...) (.....) (...X.) (.....) (XX...) (.....)
(XXX..) (.....) (..XXX) (.....) (..X..) (.....)
f (...X.) = (.....), f (.X...) = (.....), and f (X.XX.) = (.....)
(XX.XX) (.....) (XX.XX) (.....) (X.X.X) (.....)
(...X.) (XXX..) (.X...) (..XXX) (...XX) (X...X)
{X} {Y} {Z}
we can get solutions to all 8 solvable bottom rows by taking linear
combinations of the three solutions above. Thus since f(X+Y) = f(X) +
f(Y), we can add X and Y from above to get:
[(.X...) (...X.)] (.X.X.) (.....)
[(XXX..) (..XXX)] (XX.XX) (.....)
f [(...X.) + (.X...)] = f (.X.X.) = (.....)
[(XX.XX) (XX.XX)] (.....) (.....)
[(...X.) (.X...)] (.X.X.) (XX.XX)
{X} {Y} {P+X+Y}
Thus,
[(.....) (.X.X.)] (.X.X.) (.XXX.)
[(.XXX.) (XX.XX)] (X.X.X) (X.X.X)
f [(.....) + (.X.X.)] = f (.X.X.) = (XX.XX)
[(X.X.X) (.....)] (X.X.X) (X.X.X)
[(.....) (.X.X.)] (.X.X.) (.XXX.)
{P} {X + Y}
and so we have a solution to level 1.
Finally, if we want the optimal solution, we can add the input to the
different nullspace positions and look for the one with the least
number of lights. Using S4, we get
[(.X.X.) (.XXX.)] (..X..) (.XXX.)
[(X.X.X) (X.X.X)] (.....) (X.X.X)
f [(.X.X.) + (XX.XX)] = f(X...X) = (XX.XX)
[(X.X.X) (X.X.X)] (.....) (X.X.X)
[(.X.X.) (.XXX.)] (..X..) (.XXX.)
{P+X+Y} {S4} {solution}
From this we know that the optimal solution is the one illustrated,
only requiring four buttons to be pressed. This solution algorithm is
exactly the one that is used in the Java game on the previous page.
Back to Lights Out.