Lights Out (игра)

Нажатие на клетку переключает состояние соседних.

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

Геймплей

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

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

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

$\mathbf A_{34} = \begin{bmatrix} 0 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 1 & 0 \\0 & 0 & 1 & 1 & 1 \\0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0\end{bmatrix}\,$

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

$\! L + \sum_{i, j} x_{ij} A_{ij} = 0$, где 0 — нулевая матрица, а x_{i, j} — количество ходов в клетку (i, j).

Поскольку все операции выполняются по модулю 2, решение может быть переписано в виде

$\! \sum_{i, j} x_{ij} A_{ij} = L$

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

$\begin{pmatrix} 1 & 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 \end{pmatrix} \begin{pmatrix} x_{11} \\ x_{12} \\ x_{13} \\ x_{21} \\ x_{22} \\ x_{23} \\ x_{31} \\ x_{32} \\ x_{33} \end{pmatrix} = \begin{pmatrix} L_{11} \\ L_{12} \\ L_{13} \\ L_{21} \\ L_{22} \\ L_{23} \\ L_{31} \\ L_{32} \\ L_{33} \end{pmatrix}$

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

См. также

• Теория групп