A Lights Out Puzzle with Solver (JavaScript)


How does it work?

In case of 6x5 grid and two colors, a bit vector x of length 30 can contain an answer. Each element of the vector corresponds to a field cell and its bit value expresses whether the cell should be pressed or not. A board state can also be stated as a bit vector b of length n = 30 where each element expresses whether the cell is lit or not.

Pressing a cell inverts the state of some cells, which is expressed as a 30-vector [a1j ... anj] where each bit aij contains whether the cell i is inverted or not by pressing the cell j. The whole effect of pressing the cells as specified by the answer vector x is determined by, for each cell i, whether the times of inversions at i is odd or even. This can be expressed as (ai1*x1 + ... + ain*xn) mod 2.

The puzzle is now stated as a problem to find an x such that

  (ai1*x1 + ... + ain*xn + bi) mod 2 = c
for all i with some final lightness c, or equivalently:
  (ai1*x1 + ... + ain*xn) mod 2 = (c - bi) mod 2
This can be solved with Gaussian elimination since mod 2 effectively distributes over anything.

---Using finite field linear algebra, this method is stated as follows:

  A x = c - b
    x = A^{-1}(c - b)
Although A^{-1} can be computed in advance for better performance, the script in this page computes A x = c - b every time.