On a N×N board, all lights are initially white. By clicking a light, the color of this light and four adjacent ones (up,down,left,right) will be flipped (from red to white, or from white to red). The aim is to turn all lights to red.
Note, the "Solve" button in the demonstration enumerates all solutions. The algorithm used here is quite simple.
First of all, the order of operations does not matter, and clicking the same square twice annihilates the operations. Thus, each configuration can be reached by clicking each square at most once. The total number of final configurations is no larger than 2N×N.
Given a particular combination of clicks of the first row, there is only one combination of clicks for the second row that turns on all missing lights of the first row. Similiarly, the third, fourth, ..., last rows are all successively determined. Thus the configuration of the whole board is simply determined by the states of the first row squares. However, given an arbitrary state of the first row, the procedure does not guarantee that lights on the last row are all turned on. We therefore need to enumerate all possibilities of the first row. Hence the complexity is reduced to 2N.
To make the iteration faster, we used bit-wise operations in transitions between rows. The remaining task is just to enumerate all possible combinations of the first row. a minimalist C version (32-bit integer version, only for N < 32).
This algorithm works well for a small N, but is bad for large N. A better way is to use Gaussian elimination to inverse the neighboring matrix.