Гаснет свет (игра)
 | Эта статья нуждается в дополнительных цитатах для проверки . ( ноябрь 2010 г. ) |
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]
Изобретатели
[ редактировать ] | Этот раздел нуждается в дополнительных цитатах для проверки . ( Ноябрь 2010 г. ) |
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]
Доказано существование решений для самых разных конфигураций плат, таких как шестиугольная, [9] в то время как решения для досок размером n×n для n≤200 были явно построены. [10]
Существует решение для каждого случая N×N. Ее можно решить на любом неориентированном графе, где нажатие на одну вершину меняет ее значение и ее соседей. В более общем смысле, если матрица действий симметрична, то ее диагональ всегда разрешима. [11]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Перейти обратно: а б с д «Beyond Tetris» — Lights Out , Тони Дельгадо, GameSetWatch , 29 января 2007 г. Доступ онлайн 18 октября 2007 г.
- ^ Перейти обратно: а б с Гаснет свет , страница головоломки Яапа. Доступ онлайн 18 октября 2007 г.
- ^ «Загадка по программированию: переключение света» . 13 декабря 2020 г.
- ^ «Архив интересного кода» . www.keithschwarz.com . Проверено 12 июня 2020 г.
- ^ Перейти обратно: а б Вайсштейн, Эрик В. «Загадка с выключением света» . Математический мир .
- ^ Перейти обратно: а б с д Марлоу Андерсон, Тодд Фейл (1998). «Выключаем свет с помощью линейной алгебры» (PDF) . Журнал «Математика» . 71 (4): 300–303. дои : 10.1080/0025570X.1998.11996658 . Архивировано из оригинала (PDF) 15 августа 2014 года.
- ^ Эйзель, Роберт (30 июля 2018 г.). «Решение LightsOut с использованием линейной алгебры» . Проверено 20 марта 2024 г.
- ^ Перейти обратно: а б с Решение проблемы отключения света , Мэтью Бэйкер.
- ^ неизвестно (20 ноября 2010 г.). «Игра гаснет на шестиугольной сетке» . Проверено 30 ноября 2010 г.
- ^ Джим Фаулер (21 июля 2008 г.). «Решения для отключения света» . Блог Джима Фаулера . Проверено 30 ноября 2010 г.
- ^ Игорь Миневич (2012). «Симметричные матрицы над F_2 и проблема отключения света». arXiv : 1206.2973 [ math.RA ].