Lights Out

An electronic game where the goal is to turn off all the lights.

This electronic puzzle consists of a 5-by-5 grid of lights; when the game starts, a set of these lights (random, or one of a set of stored puzzle patterns) are switched on. Pressing one of the lights will toggle it, and the four lights adjacent to it, on and off. The game provides a puzzle: given some initial configuration where some lights are on and some are off, the goal is to switch all the lights off, preferably in as few button presses as possible.

The applet below was written by Jaap Scherphuis © ( Jaap's Puzzle Page).

Lights Out Matrix

In Lecture 24 of the course notes we show that: writing $\boldsymbol{b}=(b_{1,1}, b_{1,2},b_{1,3}, \ldots, b_{4,5}, b_{5,5})$ for the $25$ dimensional vector representing the light configuration (entries are $1$ if the light at position $(i,j)$ is on, $0$ if off), a strategy vector $\boldsymbol{x}$ for solving the puzzle is a solution to matrix equation (over the finite field $\mathbb{F}_2$) $$A\boldsymbol{x} =\boldsymbol{b}$$ where $A$ is the $25\times 25$ matrix whose columns are the toggle vectors $\boldsymbol{t}_{k,\ell}=(t_{1,1}, t_{1,2}, \ldots, t_{4,5}, t_{5,5})$ (entry $(i,j)$ is $1$ if pressing button $(k,\ell)$ toggles light $(i,j)$, or $0$ otherwise): $$A=\left[\boldsymbol{t}_{1,1}~|~\boldsymbol{t}_{1,2}~|~\cdots ~|~ \boldsymbol{t}_{5,5} \right].$$ We can write $A$ as $$A= \begin{bmatrix} C & I_5 & 0 & 0 & 0 \\ I_5 & C & I_5 & 0 & 0 \\ 0 & I_5 & C & I_5 & 0 \\ 0 & 0 & I_5 & C & I_5 \\ 0 & 0 & 0 & I_5 & C \end{bmatrix} \quad\quad \text{ (lights out matrix)}$$ where $C$ represents the $5\times 5$ matrix $$C= \begin{bmatrix} 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 \end{bmatrix}$$ and $I_5$ denotes the $5\times 5$ identity matrix. The matrix $A$ is referred to as the lights out matrix. Using the command block_matrix() we can input $A$ into SageMath as follows.

xxxxxxxxxx

C=matrix(GF(2),5,5,[1,1,0,0,0, 1,1,1,0,0, 0,1,1,1,0, 0,0,1,1,1, 0,0,0,1,1])

I5=identity_matrix(5)

A=block_matrix([[C,I5,0,0,0],[I5,C,I5,0,0],[0,I5,C,I5,0],[0,0,I5,C,I5],[0,0,0,I5,C]])

​

print(A.str())   # this forces SageMath to print matrix to screen

The above implementation of $A$ is fine for analyzing the $5\times5$ puzzle but we'd like to do a general analysis for different sized game boards. In this case it will be useful for us to implement $A$ as a function which takes the size of the board as input. We can do this as follows.

xxxxxxxxxx

# Definition of the matrix for Lights Out

# input = integer n (where lights out board is nxn)

# output = lights out matrix A which is n^2 x n^2

def lights_out(i):

    # create block C first

    C=identity_matrix(GF(2),i)

    C[1:i,0:i-1]=C[1:i,0:i-1]+identity_matrix(GF(2),i-1)  # block below diagonal

    C[0:i-1,1:i]=C[0:i-1,1:i]+identity_matrix(GF(2),i-1)  # block above diagonal

    # now build A as a block matrix from C's and I's

    A=identity_matrix(GF(2),i^2)

    for j in [0..i]:

        A[j*i:(j+1)*i,j*i:(j+1)*i]=C  # block on diagonal

    for j in [1..i-1]:

        A[j*i:(j+1)*i,(j-1)*i:j*i]=identity_matrix(GF(2),i)  # block below diagonal

        A[(j-1)*i:j*i,j*i:(j+1)*i]=identity_matrix(GF(2),i)  # block above diagonal

    return A

​

# Example: 3x3 lights out matrix

lights_out(3)

An alternative construction for $A$ is given below (this is also the one found in the course textbook). You can use either one, just try to undertand the construction in either case.

xxxxxxxxxx

# Definition of the matrix for Lights Out

# input = integer n (where lights out board is nxn)

# output = lights out matrix A which is n^2 x n^2

def lights_out(n):

    A = identity_matrix(GF(2),n*n)     # initialize A with ones along diagonal

    for i in range(n):

        for j in range(n):

            m = n*i+j

            if i > 0 : A[(m,m-n)] = 1   # I block below diagonal

            if i < n-1 : A[(m,m+n)] = 1 # I block above diagonal

            if j > 0 : A[(m,m-1)] = 1   # C block below diagonal

            if j < n-1 : A[(m,m+1)] = 1 # C block above diagonal

    return A

​

# Example: 3x3 lights out matrix

lights_out(3)

Lights Out Solver

Here is an implementation of a lights solver. Scroll to the bottom of the code block for an example.

xxxxxxxxxx

# Definition of the matrix for Lights Out

# input = integer n (where lights out board is nxn)

# output = lights out matrix A which is n^2 x n^2

def lights_out(n):

    A = identity_matrix(GF(2),n*n)     # initialize A with ones along diagonal

    for i in range(n):

        for j in range(n):

            m = n*i+j

            if i > 0 : A[(m,m-n)] = 1   # I block below diagonal

            if i < n-1 : A[(m,m+n)] = 1 # I block above diagonal

            if j > 0 : A[(m,m-1)] = 1   # C block below diagonal

            if j < n-1 : A[(m,m+1)] = 1 # C block above diagonal

    return A

​

​

# Function:  number_of_presses

# input = a vector x of dimension 25 with 0,1 entries

# output = the number of times 1 appears as an entry

def number_of_presses(x):

    counter=0;

    for i in range(0,25):

        if x[i]==1: counter=counter+1

    return counter

​

# Function:  optimal_solution

# input = a strategy vector x

# output = an equivalent strategy vector which uses the minimum number of button presses

def optimal_solution(x):

    op_button_presses=x

    n=number_of_presses(x)

    nul=lights_out(5).right_kernel()

    for d in nul:

        if number_of_presses(x+d)<n:

            op_button_presses=x+d     # update variable

            n=number_of_presses(x+d)  # update variable

    return op_button_presses

​

# Function:  lights_out_solver

# input = b the configuration vector of lights on 5-by-5 game

# output = a matrix which solve the puzzle using the least number of button presses

def lights_out_solver(b):

    x=lights_out(5).solve_right(b);  # one solution

    x=optimal_solution(x)     # exchanges x for an optimal solution

    button_press_matrix = matrix(GF(2),5,5,x.list())

    return button_press_matrix

​

# Example

b=vector(GF(2),[1,0,0,0,0, 1,0,1,0,1, 1,0,0,0,1, 1,0,1,0,1, 0,0,0,0,1]);

lights_out_solver(b)

Lights Out Variation - 3 states of lights

A variation of the game in which each light has $3$ states (red, green, off) was marketed as Lights Out 2000. The toggle criteria is the same: pressing a button toggles the state of the button pressed and its horizontal and vertical neighbours. The lights cycle through the states red to green to off.

You can play around with this version here. This applet was written by Jaap Scherphuis © ( Jaap's Puzzle Page).

Lights Out Variation - Different Toggle Patterns and Board Sizes

Jaaps Puzzle Page (lights out) contains tons of information about variations of the puzzle. Try this applet (Lights Out Variations) which allows you to change the board size and toggle patterns. You can try out a cross pattern (x) instead of the classic plus pattern (+).