# Light Out Puzzle Solution

I am decided to solve the puzzle game named Lights out. So, i choose linear-algebra to solve my problem, so note that this link, i start my work as follow :

NOTE : Any light states can accept two values, on = 1 and off = 0, {0,1} and all calculation will be done in this set.

1. The summation operator used in theorem is : 1 + 1 = 0 + 0 = 0 and 1 + 0 = 0 + 1 = 1

2. The multiplication operator used in theorem is : 1 * 1 = 1 and else are 0.

3. For each action v, we can prove that v + v = 0 (using summation operator)

• v is the 5x5 matrix shows the light status.
4. Each button should be pressed at once. ( v + v = 0 )

5. All of computing can be done in modulo 2. (on and off)

6. Suppose matrix Act_i which pressing i'th button in Zero-Matrix, converts this matrix to Act_i. For example Act_10, converts Zero-Matrix (5x5) to :

0 0 0 0 1
0 0 0 1 1
0 0 0 0 1
0 0 0 0 0
0 0 0 0 0

1. I show the initial state of puzzle table (5x5) in row-matrix. (25x1)

• Row matrix B = (b1, b2, b3, ..., b25)
2. Suppose that matrix X is the matrix that we should pressed to convert matrix Bto Zero matrix. (the goal of problem)

3. Suppose Matrix A that is 25x25 matrix and i'th row of this matrix equals to Act_i (look at 6)

Finally, i have the equation AX = B that we can solve it easily. I tried to solve this using the matrix library in Java. But, this work wrong to solve the solution.

Example:

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


B =

0
1
0
1
1
0
0
1
1


But, my computational X is equals to : X =

 1.285714
-0.142857
-0.714286
-1.142857
0.571429
0.857143
0.285714
0.857143
-0.714286


But it is wrong, because of this solution.

1
1
1
0
0
0
0
0
1


Could any one tell me what thing is wrong ? Why my calculation answer is wrong ?!

We can't say. You have a given $A$ and $b$, and you are supposed to solve for $x$ so that $Ax = b$. The system is set up correctly, but we don't know how you actually computed it. So we can't fix your computation. – mixedmath Jul 16 '12 at 18:34
Presumably Java's matrix library is set up to do matrix computations over $\Bbb{R}$ or $\Bbb{C}$. The lights-out puzzle forms a vector space over $\Bbb{Z}/2$. stackoverflow.com/questions/7916493/… has some links to libraries that'll do what you want; one in C++ and one in Java (though they might be more high-powered than you need). – Micah Jul 16 '12 at 18:35
@HenningMakholm is right. A fix might be to multiply the result by the determinant (which in this case is $\pm 7$, i didn't check which) and then take everything mod $2$. You'll get what you're looking for. – Cocopuffs Jul 16 '12 at 18:41