Lights Out (игра)

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

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

Геймплей

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

Компьютерные реализации

• Curly Molly Lights out game Архивная копия от 7 марта 2016 на Wayback Machine — оригинальная реализация игры для iOS устройств.
• Lights OFF Архивная копия от 4 октября 2014 на Wayback Machine — современная реализация для Android устройств.

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

Каждая конфигурация поля может быть записана как матрица L размера 5x5, содержащая нули и единицы. Ход в клетку (i, j) соответствует прибавлению к матрице L матрицы A_ij по модулю 2, в которой элемент (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), в противном случае такого хода не делается. Случаи иных размерностей рассматриваются аналогично.

См. также

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

Ссылки

• Онлайн версия головоломки Lights Out Архивная копия от 12 августа 2017 на Wayback Machine