LightsOut game solving method "reduced echolean ".Does it always gives correct result?

Question

I am studing the algorithm given here, and somewhere it is claimed that it is efficent and always give correct result.

But, I try to run the algorithm and it is not giving me correct or efficent output for the following patterns. For 5 x 5 grid, where (n) is light number and 0/1 state whethere the light is on/off, 1 ON and 0 OFF.

(1)1    (2)0    (3)0    (4)0    (5)0      the output should be 1,7,13,19,25(Pressing this light will make the full grid OFF. But what I am getting is this  
(6)0    (7)1    (8)0    (9)0    (10)0     3,5,6,7,8,10,13,16,18,19,20,21,23. 
(11)0   (12)0   (13)1   (14)0   (15)0      
(16)0   (17)0   (18)0   (19)1   (20)0
(21)0   (22)0   (23)0   (24)0   (25)1

While for some pattern it is giving me correct output as below.

    (1)0    (2)0    (3)0    (4)0    (5)1      the output should be 5,9,13,17,21, and the algorithm is giving me correct result. 
    (6)0    (7)0    (8)0    (9)1    (10)0      
    (11)0   (12)0   (13)1   (14)0   (15)0      
    (16)0   (17)1   (18)0   (19)0   (20)0
    (21)1   (22)0   (23)0   (24)0   (25)0

If somebody need a code let me know I can post it.

Can please somebody let me know if this methods will always give correct as well as efficient result or not ?

Answer 1

(I'm the author of the code you linked to.) To the best of my knowledge, the code is correct (and I'm sure that the high-level algorithm of using Gaussian elimination over GF(2) is correct). The solution it produces is guaranteed to solve the puzzle, though it's not necessarily the minimal number of button presses. The "efficiency" I was referring to in the writeup refers to the time complexity of solving the puzzle overall (it can solve a Lights Out grid in polynomial time, as opposed to the exponential-time brute-force solution of trying all possible combinations) rather than to the "efficiency" of the generated solution.

I actually don't know any efficient algorithms for finding a solution requiring the minimum number of button presses. Let me know if you find one!

Hope this helps!