Lights Out (игра)

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

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

Геймплей

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

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

• 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) и соседние к нему равны единице, а все остальные равны нулю. Например:

${\displaystyle \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}}}$

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

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

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

${\displaystyle \sum _{i,j}x_{ij}A_{ij}=L}$

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

${\displaystyle {\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), в противном случае такого хода не делается. Случаи иных размерностей рассматриваются аналогично.^[3]

См. также

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

Примечания

1. 'Beyond Tetris' — Lights Out Архивная копия от 24 сентября 2015 на Wayback Machine, Tony Delgado, GameSetWatch, January 29, 2007. Accessed on line October 18, 2007.
2. Lights Out Архивная копия от 26 февраля 2015 на Wayback Machine, Jaap’s Puzzle Page. Accessed on line October 18, 2007.
3. Weisstein, Eric W. Lights Out Puzzle (англ.) на сайте Wolfram MathWorld.

Ссылки

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