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