4
$\begingroup$

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.

Answer X =

1 1 1 0 0 0 0 0 1 

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

Thanks in advance :)

  • 1
    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.2012-07-16
  • 1
    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$. http://stackoverflow.com/questions/7916493/solving-equation-systems-over-finite-fields 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).2012-07-16
  • 3
    Results like 1.285714 doesn't sound like you're doing the computation modulo 2, such as you decided to.2012-07-16
  • 0
    @Micah: thanks for your comment and link :)2012-07-16
  • 3
    @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.2012-07-16
  • 0
    @HenningMakholm: Thank for your note :)2012-07-16
  • 0
    @Cocopuffs: i try to solve this problem. Thanks :)2012-07-16

0 Answers 0