Lights Out (игра)

Материал из Википедии — свободной энциклопедии
(перенаправлено с «Lights out (игра)»)
Перейти к: навигация, поиск
Нажатие на клетку переключает состояние соседних.

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

Геймплей[править | править вики-текст]

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

Компьютерные реализации[править | править вики-текст]

Математическая постановка[править | править вики-текст]

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

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

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

Поскольку xi, j может быть равен нулю или единице, то решение может быть переписано в виде системы n2 линейный уравнений, где 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}

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

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. 1 2 3 4 'Beyond Tetris' — Lights Out, Tony Delgado, GameSetWatch, January 29, 2007. Accessed on line October 18, 2007.
  2. 1 2 Lights Out, Jaap’s Puzzle Page. Accessed on line October 18, 2007.
  3. Lights Out Puzzle, MathWorld.