Русская Википедия:Lights Out (игра)
Lights Out (дословно: «тушите свет») — электронная игра, созданная Tiger Toys в 1995 году.[1] Игра содержит поле 5x5, каждая клетка которого может быть в состоянии «включено» или «выключено». Нажатие на любую клетку поля изменит состояние этой и четырёх соседних клеток. Цель игры — перевести всё поле в состояние «выключено» за как можно меньшее число ходов.[1][2] Также существуют игры, работающие по тому же принципу, но с иным размером или формой поля.[1][2]
Геймплей
Как только игра начинается, на поле случайным образом несколько элементов переходят в состояние «включено». Нажатие на любую клетку поля изменит состояние этой и четырёх соседних клеток. Цель игры — перевести всё поле в состояние «выключено».[1]
Компьютерные реализации
- Curly Molly Lights out game Шаблон:Wayback — оригинальная реализация игры для iOS устройств.
- Lights OFF Шаблон:Wayback — современная реализация для Android устройств.
Математическая постановка
Каждая конфигурация поля может быть записана как матрица L размера 5x5, содержащая нули и единицы. Ход в клетку (i, j) соответствует прибавлению к матрице L матрицы Aij по модулю 2, в которой элемент (i, j) и соседние к нему равны единице, а все остальные равны нулю. Например:
- <math>
\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}</math> Поскольку сложение матриц коммутативно, то решение не зависит от порядка ходов. Результат каждой последовательности нажатий может быть записан в виде:
- <math>L + \sum_{i, j} x_{ij} A_{ij} = 0</math>, где 0 — нулевая матрица, а xi, j — количество ходов в клетку (i, j).
Поскольку все операции выполняются по модулю 2, решение может быть переписано в виде
- <math>\sum_{i, j} x_{ij} A_{ij} = L</math>
Поскольку xi, j может быть равен нулю или единице, то решение может быть переписано в виде системы n2 линейных уравнений, где n — размерность матрицы L. Эта система для случая 3x3 имеет вид
- <math>
\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}. </math> Если xij = 1, то делается ход в клетку (i, j), в противном случае такого хода не делается. Случаи иных размерностей рассматриваются аналогично.[3]
См. также
Примечания
Ссылки
- ↑ 1,0 1,1 1,2 1,3 'Beyond Tetris' — Lights Out Шаблон:Wayback, Tony Delgado, GameSetWatch, January 29, 2007. Accessed on line October 18, 2007.
- ↑ 2,0 2,1 Lights Out Шаблон:Wayback, Jaap’s Puzzle Page. Accessed on line October 18, 2007.
- ↑ Шаблон:MathWorld