Войти
Выбор квадрата изменяет его и окружающие квадраты. Lights Out - это электронный игра выпущена Tiger Electronics в 1995 году. Игра состоит из сетки огней 5 на 5. Когда игра начинается, включается случайное число или сохраненный рисунок этих огней. Нажатие любого из индикаторов переключит его и соседние индикаторы. Цель головоломки - выключить все огни, желательно с помощью как можно меньшего числа нажатий кнопок.
Merlin, похожая электронная игра, была выпущена Parker Brothers в 1970-х годах с аналогичные правила на сетке 3 на 3. Еще одна похожая игра была выпущена Vulcan Electronics в 1983 году под названием XL-25. Tiger Toys также выпустила версию Lights Out на картриджах для своей портативной игровой консоли Game com в 1997 году, которая поставляется бесплатно с консолью. Был выпущен ряд новых головоломок, похожих на Lights Out, например Lights Out 2000, Lights Out Cube и Lights Out Deluxe.
Lights Out был создан группой людей, включая Ави Олти, Дьора Бенедек, Цви Херман, Ревиталь Блумберг, Ави Вайнер и Майкл Ганор. Члены группы вместе и по отдельности также изобрели несколько других игр, таких как Hidato, NimX, iTop и многие другие.
Игра состоит из сетки огней 5 на 5. Когда игра начинается, включается случайное число или сохраненный рисунок этих огней. Нажатие любого из индикаторов переключит его и четыре соседних индикатора. Цель головоломки - выключить все огни, желательно за как можно меньше нажатий кнопок.
Если свет горит, его нужно переключать нечетное количество раз быть выключенным. Если свет не горит, его нужно переключить четное количество раз (в том числе ни одного), чтобы он оставался выключенным. Для стратегии игры используются несколько выводов. Во-первых, порядок нажатия лампочек не имеет значения, результат будет таким же. Во-вторых, в минимальном решении на каждую лампу нужно нажимать не более одного раза, потому что нажатие на лампу дважды эквивалентно тому, чтобы не нажимать на нее вообще.
В 1998 году Марлоу Андерсон и Тодд Фейл использовали линейную алгебру для доказать, что не все конфигурации разрешимы, а также доказать, что существует ровно четыре выигрышных сценария, не считая избыточных ходов, для любой решаемой задачи 5 × 5. Сетка 5 × 5 для Lights Out может быть представлена как вектор-столбец 25x1 с 1 и 0, обозначающими свет во включенном и выключенном состоянии соответственно. Каждая запись является элементом Z2, поля целых чисел по модулю 2. Андерсон и Фейл обнаружили, что для того, чтобы конфигурация была разрешимой (получение нулевого вектора из исходной конфигурации), она должна быть ортогональна двум векторам N 1 и N 2 ниже ( изображенный как массив 5 × 5, но не путать с матрицами).
Кроме того, они обнаружили, что N 1 и N 2 можно использовать, чтобы найти три дополнительных решения к решению, и что эти четыре решения являются единственными четырьмя решениями (за исключением избыточных перемещений) для исходной данной конфигурации. Эти четыре решения: X, X + N 1, X + N 2 и X + N 1 + N 2, где X является решением исходной данной конфигурации. Введение в этот метод было опубликовано Робертом Эйзеле.
«Погоня за светом» - это метод, аналогичный Гауссову исключению, который всегда решает загадку (если решение существует), хотя с возможностью многих повторений шаги. В этом подходе строки обрабатываются по одной, начиная с верхней строки. Все источники света в строке отключаются путем переключения соседних источников света в строке непосредственно под ним. Затем тот же метод применяется к последовательным строкам вплоть до последней. Последний ряд решается отдельно, в зависимости от его активных огней. Соответствующие индикаторы (см. Таблицу ниже) в верхней строке переключаются, и снова запускается первоначальный алгоритм, что приводит к решению.
| Нижняя строка: | Переключение в верхней строке |
|---|---|
| ⬜⬜⬜⬛⬛ | ⬛▣⬛⬛⬛ |
| ⬜⬜⬛⬜⬜ | ⬛⬛▣⬛⬛ |
| ⬜⬛⬜⬜⬛ | ⬛⬛⬛⬛▣ |
| ⬜⬛⬛⬛⬜ | ▣▣⬛⬛⬛ |
| ⬛⬜⬜⬛⬜ | ▣⬛⬛⬛⬛ |
| ⬛⬜⬛⬜⬛ | ▣⬛⬛▣⬛ |
| ⬛⬛⬜⬜⬜ | ⬛⬛⬛▣⬛ |
Таблицы и стратегии для других размеров доски генерируются путем игры Lights Out с пустой доской и наблюдения за результатом перенести конкретный свет из верхнего ряда вниз в нижний ряд.
После того, как единственное решение найдено, решение с минимальным числом ходов может быть определено путем исключения избыточных наборов нажатий кнопок, которые не имеют кумулятивного эффекта. Если головоломка 5 × 5 неразрешима при легальном создании игры, два крайних левых индикатора в нижнем ряду останутся включенными, когда все остальные индикаторы будут выключены.
Существование решений было доказано для широкого спектра конфигураций плат, таких как шестиугольные, в то время как решения для плат n × n для n≤200 были явно построены.
Существует решение для любого случая N × N. Он разрешим на любом неориентированном графе, где щелчок по одной вершине переворачивает ее значение и ее соседи. В более общем смысле, если матрица действий симметрична, то ее диагональ всегда разрешима.
