"Light's Out" Game and Its Solution with Linear Algebra

Hi reader, this is my first article that is written in English here. Why I am writing in English? Actually, I want to share my reports and projects that I found interesting during the master. All reports and projects are of course in English. So, I don't want to translate these subject to Turkish. If you don't know English but want to learn more about. You can ask everything about the related subject. Today, I am going to talk about "Light's Out" game and its solution with "Linear Algebra". If you know Linear Algebra and how to apply it to the game, then it is just 10-15 lines of code. I am also going to share the MATLAB solution end of the article.

Chapter 1: Abstract

1. Preliminary

Light out is a game introduced by tiger electronics, an American toy manufacturer, on a 5 by grid matrix, where each matrix can have either on or off status? The game begins with some of the matrices turned on randomly. Pressing a single buttons will affect the status of itself and its neighbors. The game of the game is to systematically press as much as possible less number of times and making every matrices become off.[1][2]

The goal of the game is to turn all of the lights off. The goal of the puzzle is to switch all the lights off, preferably in as few button presses as possible. Every time a button is pressed, the state of that button as well as the state of the buttons above, below and to the left and right are changed. For example, if all buttons are turned off and a button is pressed, the resulting outcome could result in three, four, or five buttons lighting up depending upon where the original button was located on the game board.[4]

Chapter 2: Mathematical Modeling

1. Why it can be solved by linear Algebra

There are two typical features for the solution of the game. First, each button just need to be pushed once, in other words no more than once because double push equals no push. Second, the order of pushing is not important because the state of a button depends only on how many times it be turned. With these two features, we can say that the solution of the lights matrix can be given by a matrix. That means it’s the problem of Ax = b, where A is the game system, x is the strategy vector, b is the respond of the game system after appliying strategy vector.

2. Game System and Button Pushing Operation

First, Let’s look at a random strategy vector:

x = [ 1 0 0 1 0 1 0 0 0 ... ] ^T

Refer to the feature of matrix multiplication, when we multiply A with x, strategy vector x actually choose some columns of A while the elements of other columns multiply 0 in x. In that case, we can connect the columns of A with the respond of button appliying strategy.

Let’s start with a 3x3 matrix because it is easy and also can be the minimum lights matrix of the game.

LightsMatrix

0 0 0

0 0 0

0 0 0

If the first element of the vector x is 1, then our lights matrix is going to be like this:

LightsMatrix

1 1 0

1 0 0

0 0 0

Let’s reshape the Lights Matrix into one column, if the first element of the vector x is 1:

Col₁^T = [ 1 1 0 1 0 0 0 0 0 ]

Repeat the above work until get 9 Columns which means each button has a column contain the

information of system response.

Col₁^T = [ 1 1 0 1 0 0 0 0 0 ]

Col₂^T = [ 1 1 1 0 1 0 0 0 0 ]

Col₃^T = [ 0 1 1 0 0 1 0 0 0 ]

Col₄^T = [ 1 0 0 1 1 0 1 0 0 ]

Col₅^T = [ 0 1 0 1 1 1 0 1 0 ]

Col₆^T = [ 0 0 1 0 1 1 0 0 1 ]

Col₇^T = [ 0 0 0 1 0 0 1 1 0 ]

Col₈^T = [ 0 0 0 0 1 0 1 1 1 ]

Col₉^T = [ 0 0 0 0 0 1 0 1 1 ]

Then the matrix A is given by:

A = [ Col₁ Col₂ Col₃ Col₄ Col₅ Col₆ Col₇ Col₈ Col₉ ]

A

1 1 0 1 0 0 0 0 0

1 1 1 0 1 0 0 0 0

0 1 1 0 0 1 0 0 0

1 0 0 1 1 0 1 0 0

0 1 0 1 1 1 0 1 0

0 0 1 0 1 1 0 0 1

0 0 0 1 0 0 1 1 0

0 0 0 0 1 0 1 1 1

0 0 0 0 0 1 0 1 1

Let’s define some matrices:

B

1 1 0

1 1 1

0 1 1

I

1 0 0

0 1 0

0 0 1

O

0 0 0

0 0 0

0 0 0

Then let’s reshape matrix A;

A

B I O

I B I

O I B

Then the problem Ax = b means that A is the system response matrix that each column mapping a response of a button appliying strategy. Vector x is our strategy, and the element 1 means pushing the corresponding button. Vector b is the response after doing operation x.

The responding of game system is the linear combination of the button appliying strategy. For checking, let push the first and last button which means

x = [ 1 0 0 0 0 0 0 0 1 ]^T

.

Ax = b = [ 1 1 0 1 0 1 0 1 1]^T

Reshape b into the lights matrix:

LightsMatrix

1 1 0

1 0 1

0 1 1

3. What is the strategy of the game?

We know A is the response system assumed all lights is off. Consequently, A is our goal, b is the A after strategy x, let b is the random lights matrix we have. Since the button just have two states, it is the same operation x to get A from b. Vector x is the strategy to turn the random b to the zero one.

Example 1:

LightsMatrix

1 0 0

1 1 1

1 1 1

Obviously, the strategy vector is

x = [ 0 0 0 1 0 0 0 0 1 ] ^T

If we solve the problem Ax = b, where b is the vector by reshaping Lights Matrix.

b = [ 1 0 0 1 1 1 1 1 1 ]^T

The solution of Ax = b is

x = [ 0 0 0 1 0 0 0 0 1 ] ^T

Hence, the solution of Ax = b is the solution of the game.

Chapter 3: Solving the Game

1. Solvability Condition

We can see that maxtrix B, identitiy matrix I and zero matrix O is:

B = B^T , I = I^T ,O = O^T

Which makes A transpose to equal A, and thus A is symmetric. In symmetrix matrices, like A, we can say that column space of A is equal to row space of the A. Other thing is, b matrix, our initial configuration should be in the column space of A if it is orthogonal to the null space of A.We can show it by dot producting b with all the elements of the nullspace A to check if we get 0.

In order to solve this problem we needed to use RREF where all the operations should had to be in modulo 2, where we needed to implement binary RREF.(Actually, we found this function on the web when we write the MATLAB code)

Now, assume that we have a 25x25 matrix A. In RREF, we get matrix A and strategy vector b put them into augmented matrix, and reducing/eliminating only the first 25 column, where 26th column representing b, is exposed to only row operations. After that we will see that A has 2 free columns which makes rank of A 23. This means that we have 2 variable that we can assign values freely to obtain vectors forming the nullspace.

[ 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0 ] ^T
[ 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0 ]^T

and then we give 1 and 0 to free variables

s1 = [ 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0 ] ^T

s2 = [ 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1 ] ^T

And we now have null space to check b against solvability.

2. Solutions and Solving the Game

We figured out that we can check b for solvability and accepting here x has a solution. 

However with 25x25 matrix A, rank(A) = 23, we have 2 free variables, providing 2 vectors to nullspace where we can find solutions with linear combination of them.

A(x + a.s1 + b.s2) = b

Ax + A.a.s1 + A.b.s2 = b

Ax + 0 + 0 = b

Ax = b

a, b = 1, 0 s1, s2 belongs to N(A)

So by the 2 vector we have 4 solutions to have

x

x + s1

x + s2

x + s1 + s2

So to get one of the our solution we put A and b into augmented matrix and use our binary RREF. After the elimination, the 26th column of the augmented matrix is becomes the our strategy vector representing x.

Finally we get a strategy of 25x1 matrix, where it can be think of a representation of a 5x5 game board, have values 1 representing pushes needed and 0 that not require any push.

3. Result and Discussion

Generate random configuration(Initial pattern), ¡n1.b¿ = 0 and ¡n2.b¿ = 0 if not the code is made to generate another b until b satisfies the equation.(By pushing Reset and Generate buttons) 

If it is zero for the two cases that means b is solvable the code give you detail steps how to solve for the given configuration.

In this case the game can be solved in 7 steps for the given configuration. The code guide you which buttons to press during each steps. Similarly for the next steps.

MATLAB SOLUTION

REFERENCES

1 - Light out Andrienne F.Olson April 16, 2007

2 - Turning Lights out with Linear Algebra Marlow Anderson; Todd Feil Mathematics megazine, Vol.71, No.4(Oct 1998), pp. 300-303

3 - http://en.wikipedia.org/wiki/File:LightsOutIllustration.svg

4 - A New Look at an Old Game - Lights Out Andrew Eben