In this document, I will attempt to explain how my solver works. But before I begin, there are a few properties of the game which must be understood.
Let's look at the top left button, . The state of this light is determined by how many times we push it and its neighbors, and . If the total number of presses of these three buttons is even, the light will be off. If it's odd, the light will be on. Now let's look at , right in the middle of the board. The same applies here, except that there are 5 buttons which will determine its final state: , , , , and .
To express this mathematically, we could say
Where represents the number of times we press button , and is the state of the light afterwards. We can write equations like this for all 25 buttons, which would give us a system of 25 linear equations with 25 variables. If we solve this system for a given set of states , we will have a solution to the puzzle.
To facilitate solving these equations, we will rewrite the system as a matrix and use Gauss elimination to solve the puzzle. The matrix looks like this.
The rest of the work involves setting the values for (0's and 1's) and solving the matrix using modulo 2 arithmetic. If you perform Gauss elimination on this matrix, you will find that you end up with two free variables, and . What this means is that there are four solutions, and if you want to find the shortest one, you will need to try them all. It should also be noted that not all boards have a workable solution, so you will need to test for that also.