Monday, August 27, 2007

Lights out Puzzle Revisited - the solution

Solution to the puzzle game Lights out Puzzle posted on 10th June 2007

Looking at the puzzle from a mathematical perspective, with a small board like this we can solve the problem on paper. The way would be to formulate this problem as a system of linear simultaneous equations in modulo 2 number system. Then it can be solved using gaussian ellimination or if the matrix comes out to be symmetric cholesky decomposition can also be used.
Since, for different board (bulb) configurations matrix doesn't change, a single LU (or some similar) decomposition will suffice. Once, we have such decomposition available, all board configurations can be easily solved easily on paper.

The other generic way for solving any board size for such puzzles is the following C Program based on exponential complexity!! If the problem is really solvable, the program is sufficient to do this.
Download the code here : Lights out puzzle Code in C
---