# Lights Out

This is an implementation of the semi-famous Lights Out! game. The goal is to turn off all of the lights on the board. When any cell is clicked, it and its neighbouring cells will toggle their state. Exactly which pattern of neighbours toggle can be controlled using the small board below.

Dimension of solvable space: .
Dimension of whole space: .
The probability of a totally random board being solvable is 2^{}.

## How does it work?

A lights out board can be thought of as a vector over \mathbb{F}_2, the {field}(https://en.wikipedia.org/wiki/GF(2)) containing only the elements 0 and 1, with multiplication as usual and the extra rule that 1 + 1 = 0. Adding vectors has the effect of “toggling” the numbers in the original vector on and off, for example

Try the interactive demo below, which will express the solution to any puzzle in terms of the m_{ij} vectors above.

## Generating and solving boards efficiently

Take some board configuration with n cells. By querying each cell about what it toggles on and off, form a vector corresponding to each possible move. These vectors are then assembled into an n \times n matrix M, called the *move matrix*. Gauss-Jordan Elimination is then performed to put M into reduced row-echelon form: this takes O(n^3) time, and is only done when the size or shape of the board, or thepattern of neighbours changes.

The column space of M is the subspace corresponding to all solvable boards. Using the row-reduction information for M, a basis B is extracted for this subspace in O(n^2) time. To choose a random solvable board uniformly from the space, a random 0,1-vector is chosen and multiplied onto B, which takes O(n^2) time.

Solutions to any board position can be found in O(n^2) time using the row-reduction information. What remains to be done here is to try to find a solution using the *minimum* number of moves, instead of just using any old solution.