Lights Out — электронная игра, созданная Tiger Toys в 1995 году. Игра содержит поле 5x5, каждая клетка которого может быть в состоянии «включено» или «выключено». Нажатие на любую клетку поля изменит состояние этой и четырёх соседних клеток. Цель игры — перевести всё поле в состояние «выключено» за как можно меньшее число ходов. Также существуют игры, работающие по тому же принципу, но с иным размером поля или с полем в виде куба.

Геймплей

Как только игра начинается, на поле случайным образом несколько элементов переходят в состояние «включено». Нажатие на любую клетку поля изменит состояние этой и четырёх соседних клеток. Цель игры — перевести всё поле в состояние «выключено».

Математическая постановка

Каждая конфигурация поля может быть записана как матрица L размера 5x5, содержащая нули и единицы. Ход в клетку (i, j) означает прибавление к матрице L матрицы A_ij по модулю 2, где матрица A_ij — это матрица, в которой элемент (i, j) и соседние к нему равны единице, а все остальные равны нулю. Например:
$$

\mathbf A34= \begibmatrix0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 1 & 0 \\0 & 0 & 1 & 1 & 1 \\0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0\enbmatrix,

Поскольку сложение матриц коммутативно, то решение не зависит от порядка ходов.

Каждая правильная комбинация нажатий может быть записана в виде
$\backslash !\; L\; +\; \backslash sumi,\; jxijAij=\; 0$, где 0 — нулевая матрица, а x_{i, j} — количество ходов в клетку (i, j).

Поскольку все операции выполняются по модулю 2, решение может быть переписано в виде
$\backslash !\; \backslash sumi,\; jxijAij=\; L$

Поскольку x_{i, j} может быть равен нулю или единице, то решение может быть переписано в виде системы n² линейный уравнений, где n — размерность матрицы L. Система для случая 3x3 имеет вид
$$

\begipmatrix1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\

1 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0\\

0 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0\\

1 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0\\

0 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 0\\

0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1\\

0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0\\

0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1\\

0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1

\enpmatrix

\begipmatrixx11\\ x12\\ x13\\ x21\\ x22\\ x23\\ x31\\ x32\\ x33\enpmatrix

=

\begipmatrixL11\\ L12\\ L13\\ L21\\ L22\\ L23\\ L31\\ L32\\ L33\enpmatrix

Если x_ij = 1, то есть ход в клетку (i, j). В противном случае хода нет.

Случаи иных размерностей рассматриваются аналогично.