Lights Out (игра)

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

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

Геймплей

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

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

• Curly Molly Lights out game Шаблон:Wayback — оригинальная реализация игры для iOS устройств.
• Lights OFF Шаблон:Wayback — современная реализация для Android устройств.

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

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

${𝐀}_{34}=\left[\begin{array}{ccccc}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{array}\right]$

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

$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 имеет вид

$\left(\begin{array}{ccccccccc}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{array}\right)\left(\begin{array}{c}{x}_{11}\\ x_{12}\\ x_{13}\\ x_{21}\\ x_{22}\\ x_{23}\\ x_{31}\\ x_{32}\\ x_{33}\end{array}\right)=\left(\begin{array}{c}{L}_{11}\\ L_{12}\\ L_{13}\\ L_{21}\\ L_{22}\\ L_{23}\\ L_{31}\\ L_{32}\\ L_{33}\end{array}\right).$

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

См. также

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

Ссылки

• Онлайн версия головоломки Lights Out Шаблон:Wayback