Lights Out

Lights Out#

In this presentation, I cover:

The mechanics of the Lights Out game
A playable demo
Solving the game (RREF over $\mathbb{Z}_2$)
Solvability of a game
(crux.) Size and Shape doesn’t matter
Create your own lights out grid, and have the program solve it!
Proof that the all lights-on configuration is always winnable

This is an interactive presentation (RISE). Therefore, make sure to run each cell that appears using ctrl+enter. Use the PgUp and PgDn buttons to navigate through the slides.

This presentation is heavily inspired from this video, and a chapter on the same topic; both by Nathaniel Johnston.

Mechanics of the Game#

In Lights-Out, there is a grid (typically square) with lights in each square. Each light can be in either of $2$ states - on or off. The game starts with some configuration of these lights.

The goal in Lights-Out is to turn all these lights off. The user has the ability to select lights to turn on/off. But there’s a catch!

Turning on/off a light also affects its orthogonal “neighbours”. The effect is to flip the neighbour’s states too.

import numpy as np
import matplotlib.pyplot as plt

from lights_out import *
from canvas import *

Demo#

Run the code-cell below to play the $3 \times 3$ Lights Out game!

Input the name/label of the button you want to press.

The inputs terminate when the puzzle is solved (when all the lights are off).

If you want to give up, input $-1$.

env = LightsOut([(i, j) for i in range(3) for j in range(3)])
env.play()

If you were unable to solve the $3 \times 3$ grid and would like to know a possible solution sequence, use LightsOut.solve()

env.solve()

Here’s an example on the $5 \times 5$ lights out grid. The LightsOut.illustrate_solution() method generates an animation of a possible solution:

env = LightsOut([(i, j) for i in range(5) for j in range(5)])
print('Move Sequence:', ', '.join(env.solve().astype(str)))
env.illustrate_solution(label=True)

Solving the Game#

For now, lets consider the $3 \times 3$ grid to illustrate the solution. The method can then be generalized as well.

env = LightsOut([(i, j) for i in range(3) for j in range(3)])

Encoding the configuration and actions#

The states of the 9 lights are firstly encoded in binary- $0$ for off and $1$ for on. These values are then populated into a 9-dimensional vector over $\mathbb{Z}_2$

By doing this, actions (button presses) can now be represented by vector addition. Each button press will correspond to a vector of $0$s and $1$s, where the presence of a $1$ indicates that that particular light is an orthogonal neighbour and hence, is also afected by the action.

For example, the vector toggling button $4$ (let’s call it $\mathbf{a_4}$) corresponds to:

\[ \mathbf{a_4} = (0, 1, 0, 1, 1, 1, 0, 1, 0) \]

Since pressing button $4$ affects itself, and also its orthogonal neighbours $1$, $3$, $5$, and $7$.

config = np.random.choice([0, 1], size=9)
env.displane(config, config=True)
plt.title((f'This state is encoded by: [{", ".join(np.array(config).astype(str))}]'))
plt.show()

four = np.array([0, 1, 0, 1, 1, 1, 0, 1, 0])
env.displane(np.mod(config+four, 2), config=True)
plt.title((f'Pressing 4;'))
plt.show()

Fact: The solution only depends on which buttons are pressed.

Why?

If we focus solely on just one light, then its state at the end of the game only depends on its own starting state, and the number of times the buttons corresponding to itself and its’ neighbours were pressed.
No solution may require us to press a button more than once, since pressing a button is the equivalent to not pressing at all. (This observation also re-inforces our choice of $\mathbb{Z}_2$)

Formulating the problem#

Let $\mathbf{v_s}$ and $\mathbf{v_e}$ denote the starting and intended final configurations respectively, and let $\mathbf{a_i}$ denote the $9$ different actions for our $3 \times 3$ grid. Then our goal is to find $x_1, x_2, \cdots, x_9$ such that:

\begin{align} \mathbf{v_s} + (x_1\mathbf{a_1} + x_2\mathbf{a_2} + \cdots + x_9\mathbf{a_9}) &= \mathbf{v_c}, \quad \text{or} \ x_1\mathbf{a_1} + x_2\mathbf{a_2} + \cdots + x_9\mathbf{a_9} &= \mathbf{v_e} - \mathbf{v_s} \end{align}

This is a system of linear equations. Taking $A = [\mathbf{a_1} | \mathbf{a_2} | \cdots | \mathbf{a_9}]$ we can rewrite the above system as

\[ A\mathbf{x} = \mathbf{v_e} - \mathbf{v_s} \]

For our $3 \times 3$ case, the matrix $A$ looks something like this (dots are used in-place of 0s for readability):

print_matrix(env.action_matrix, last=False)

Solving the problem#

Let $\mathbf{v_s} = 1$ and $\mathbf{v_e} = 0$ i.e, we start with the “all-lights on” configuration, and need to turn all the lights off to solve the game. Equivalently, we need to solve the linear system $A\mathbf{x} = \mathbf{v_e}-\mathbf{v_s} = 1$

We construct the augmented matrix $[A | 1]$, and obtain its reduced row-echelon form:

env.solve();
print_matrix(env.A)

print_matrix(env.A_rref)

Gauss-Jordan in $\mathbb{Z}_2$#

Below is the step-by-step visualization of Gauss-Jordan on reducing the matrix $[A|1]$.

Press Enter to go through each step. Input >> to auto-play:

env.illustrate_elimination()

From the above, setting $\mathbf{x} = (1, 0, 1, 0, 1, 0, 1, 0, 1)$ (corresponding to the $0$th, $2$nd, $4$th, $6$th and $8$th actions) is a solution for the $3 \times 3$ Lights Out puzzle.

Note that in this case, the reduced row-echelon form has the identity matrix on the left (hence full rank), which indicates that a solution always exists (alternatively, any starting configuration is always winnable). This may not always happen.

Question: What are the number of starting configurations that are winnable in the $3 \times 3$ case?

Any starting configuration is winnable; so there are $2^9$ winnable configurations.

Is the problem always solvable?#

Let’s again consider the $5 \times 5$ case, and obtain the row-reduced echelon form of its action matrix:

env = LightsOut([(i, j) for i in range(5) for j in range(5)])
env.solve();
env.illustrate_elimination(guide=False, period=0)

Observe that there are $2$ “trailing” vectors that are not part of the leading pivot matrix (free variables).

Let’s take the trailing columns (corresponding to $23$, and $24$) of the matrix and visualize it’s move sequence:

move_seq = [i for i in range(env.n) if env.A_rref[:, -3][i]]
print(move_seq)
env.illustrate_moves(move_seq, label=True)

move_seq = [i for i in range(env.n) if env.A_rref[:, -2][i]]
print(move_seq)
env.illustrate_moves(move_seq, label=True)

Note that this move sequence is exactly equivalent to pressing buttons 23 and 24 once. Buttons 23 and 24 therefore become redundant, since there exists some other combination of button presses that yield the exact same effect.

Question: What are the number of starting configurations that are winnable in the $5 \times 5$ case?

In the $5 \times 5$ case, we have 2 free-variables; buttons $23$ and $24$.
Now, let $x$ be the solution for a particular game.
Note that since buttons $23$ and $24$ are redundant buttons, we can generate 3 more solutions for the same by choosing whether to press or not press buttons $23$ and $24$.
Therefore, only $2^{25}/2^{2} = 2^{23}$ starting configurations are solvable.

The implication is that there may exist certain initial configurations that are not solvable.

However, there is a neat result:

The all $1$s configuration is always solvable!

Always; irrespective of the size, or even the shape of the LightsOut grid!

We’ll prove this lemma at the end of this presentation. But let’s experiment with this freedom of size and shape of our level first:

Size and Shape doesn’t matter!#

We can use the same row-reduction method discussed earlier on grids with any shape and size!

Try solving the below traingular puzzle. Remember, you can always give up by passing -1 as the input.

initial_state = [1, 1, 1, 1, 0, 0, 0, 0, 1]
env = LightsOut([(0, 2), (1, 1), (1, 2), (1, 3), (2, 0), (2, 1), (2, 2), (2, 3), (2, 4)])
env.play(state=initial_state)

print(env.solve(state=initial_state))
env.illustrate_solution(label=True, state=initial_state)

Create your own `LightsOut` level!#

Draw your level here…

…and have the program solve it here!

canvas

grid = (canvas.get_image_data().sum(axis=2)[:,:int(0.95*width)][::marker_size, ::marker_size] > 0).astype(int)
grid = [(i, j) for i in range(grid.shape[0]) for j in range(grid.shape[1]) if grid[(i, j)]]

env = LightsOut(grid)
env.illustrate_solution()

Statement: The “all-lights on” configuration is always winnable.

Proof: Let the action matrix be $A$. A very simplified version of the proof is as follows:

All-Lights on configuration solvable $\implies \mathbb{1} \in \mathcal{C}(A)$

Observe $A = A^T$ by construction ($A_{ij}$ is $1$ if $i$ is a neighbour of $j$, and the neighbour relation is symmetric). Thus $$\mathbb{1} \in \mathcal{C}(A) \implies \mathbb{1} \in \mathcal{C}(A^T) \implies \mathbb{1} \in \mathcal{R}(A)$$

Let $\hat{A}$ be the row echelon form of A. Note that $\mathcal{R}(A) = \mathcal{R}(\hat{A})$. Therefore $\mathbb{1} \in \mathcal{R}(A) \implies \mathbb{1} \in \mathcal{R}(\hat{A})$

Now, consider the sum of all rows in $\hat{A}$. We want this to be $\mathbb{1}$, since then $\mathbb{1} \in \mathcal{R}(\hat{A}$). This requires all columns to contain an odd number of $1$s in them (recall we are working in $\mathbb{Z}_2$).

Note this is true for all the leading columns of $\hat{A}$. Therefore, we need to show that the non-leading columns of $\hat{A}$ also have an odd number of $1$s in them.

Consider the basis for $\mathcal{N}(A)$. We can construct this basis as follows:
- For every non-leading column in $\hat{A}$:
  1. Come up with a linear combination of leading columns to construct the selected non-leading column. Note this combination is exactly the non-leading column padded with some $0$s.
  2. Set $-1$ to the index of the non-leading column in this combination. This will then yield a combination $x$ s.t. $\hat{A}x = \mathbb{0}$
Note: In $\mathbb{Z}_2, -1 \equiv 1$

Recall from the $5 \times 5$ example, where buttons $24$ and $25$ were shown to be redundant via reconstruction of the leading columns. If we perform the button sequence for button $24$, and then again press $24$, then observe that yields the all-off configuration, implying it is a part of $\mathcal{N}(A)$. This exact mechanism is described in the construction above.

Thus, we have that the number of $1$s in the null space basis is $1$ more than the number of $1$s in the non-leading column.

We wanted to show that non-leading columns contain an odd number of $1$s. Hence, it is now enough to show that all vectors of the null space have an even number of $1$s, and we’ll be done.

Let $y \in \mathcal{N}(A)$ have $k$ ones (we want to show $k$ is even). We have $Ay = \mathbb{0}$

Construct a $k \times k$ shape matrix $B$ by deleting row $j$ and column $j$ of $A$, wherever $y_j = 0$. For example:

\[\begin{split} \mathbf{y}=\left[\begin{array}{l} 0 \\ 1 \\ 1 \\ 0 \\ 1 \end{array}\right] \quad \text { and } \quad A=\left[\begin{array}{lllll} 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \end{array}\right] \quad \text { then } \quad B=\left[\begin{array}{lll} 1 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 1 & 1 \end{array}\right] \end{split}\]

Now, $Ay = \mathbb{0} \implies B\mathbb{1} = \mathbb{0}$

Observe that $B\mathbb{1}$ simply counts the number of $1$s in the rows of $B$.

Hence $B\mathbb{1} = \mathbb{0} \implies$ every row in $B$ contains an even number of $1$s.

Observe that $B$ by construction is symmetric, and all its diagonal entries are $1$ (very much like its parent matrix $A$).

Let $C = B - I$; $C$ is just $B$ but with all diagonal entries as $0$. Recall every row of $B$ had an even number of $1$s.

Hence, every row of $C$ has an odd number of $1$s. Observe that $C$ is also a symmetric $k \times k$ matrix.

From these properties of $C$, we can conclude that $k$ is even. Can you come up with a reason why?

Hint: The number of $1$s in $C$ is even. Why?

Answer:
- All diagonal entries $= 0$ and symmetry $\implies$ number of $1$s in $C$ is even.
- Number of $1$s in $C$ is even, odd number of $1$s in each row $\implies$ there are an even number of rows.
Hence $k$ is even! This completes the proof.

A backtracking summary of the proof:#

Recall $k$ was the number of $1$s in $y$, where $y \in \mathcal{N}(A)$.

$k$ is even $\implies$ all $y \in \mathcal{N}(A)$ have an even number of $1$s.

All $y \in \mathcal{N}(A)$ have an even number of $1$s $\implies$ all non-leading columns of $\hat{A}$ have an odd number of $1$s.

All non-leading columns of $\hat{A}$ have an odd number of $1$s $\implies \mathbb{1} \in \mathcal{R}(\hat{A})$ (summing up all rows of $\hat{A}$)

$\mathbb{1} \in \mathcal{R}(\hat{A}) \implies \mathbb{1} \in \mathcal{R}(A) \implies \mathbb{1} \in \mathcal{C}(A)$

Therefore the all lights on configuration is allways winnable!

Lights Out

Contents

Lights Out#

Mechanics of the Game#

Demo#

Solving the Game#

Encoding the configuration and actions#

Formulating the problem#

Solving the problem#

Gauss-Jordan in \(\mathbb{Z}_2\)#

Is the problem always solvable?#

Size and Shape doesn’t matter!#

Create your own `LightsOut` level!#

A backtracking summary of the proof:#

Lights Out

Contents

Lights Out#

Mechanics of the Game#

Demo#

Solving the Game#

Encoding the configuration and actions#

Formulating the problem#

Solving the problem#

Gauss-Jordan in \(\mathbb{Z}_2\)#

Is the problem always solvable?#

Size and Shape doesn’t matter!#

Create your own LightsOut level!#

A backtracking summary of the proof:#

Create your own `LightsOut` level!#