Lights Out (игра) - Lights Out (game)
 | Эта статья поднимает множество проблем. Пожалуйста помоги Улучши это или обсудите эти вопросы на страница обсуждения. (Узнайте, как и когда удалить эти сообщения-шаблоны) (Узнайте, как и когда удалить этот шаблон сообщения)
|
Отбой является электронная игра выпущено Тигр Электроника в 1995 г.[1] Игра состоит из сетки огней 5 на 5. Когда игра начинается, включается случайное число или сохраненный рисунок этих огней. Нажатие любого из индикаторов переключит его и соседние индикаторы. Цель головоломки - выключить все огни, желательно за как можно меньше нажатий кнопок.[1][2]
Мерлин, аналогичная электронная игра, была выпущена Братья Паркер в 1970-х с аналогичными правилами на сетке 3 на 3. Еще одна похожая игра была выпущена Vulcan Electronics в 1983 году под названием XL-25. Tiger Toys также выпустила картриджную версию Отбой для своего Game com портативная игровая консоль в 1997 году поставлялась бесплатно с консолью. Ряд новых головоломок, похожих на Отбой были выпущены, например Lights Out 2000, Lights Out Cube, и Lights Out Делюкс.[1][2]
Изобретатели
 | Эта секция нужны дополнительные цитаты для проверка. (Ноябрь 2010 г.) (Узнайте, как и когда удалить этот шаблон сообщения) |
Отбой был создан группой людей, включая Ави Олти, Дьёру Бенедек, Цви Хермана, Revital Bloomberg, Ави Вайнера и Майкла Ганора. Члены группы вместе и индивидуально также изобрели несколько других игр, таких как Хидато, NimX, iTop и многие другие.
Геймплей
Игра состоит из сетки огней 5 на 5. Когда игра начинается, включается случайное число или сохраненный рисунок этих огней. Нажатие любого из индикаторов переключит его и четыре соседних индикатора. Цель головоломки - выключить все огни, желательно за как можно меньше нажатий кнопок.[1][3]
Математика
Если свет горит, его нужно переключать нечетное количество раз, чтобы он погас. Если свет не горит, его нужно переключить четное количество раз (в том числе ни одного), чтобы он оставался выключенным. Для стратегии игры используется несколько выводов. Во-первых, порядок нажатия лампочек не имеет значения, результат будет таким же.[4] Во-вторых, в минимальном решении каждую лампу нужно нажимать не более одного раза, потому что нажатие на лампу дважды равносильно тому, что не нажимать ее вообще.[4]
В 1998 году Марлоу Андерсон и Тодд Фейл использовали линейную алгебру, чтобы доказать, что не все конфигурации разрешимы, а также чтобы доказать, что существует ровно четыре выигрышных сценария, не считая избыточных ходов, для любой решаемой задачи 5 × 5.[5] Сетка 5 × 5 для Lights Out может быть представлена как вектор-столбец 25x1 с 1 и 0, обозначающими свет во включенном и выключенном состоянии соответственно. Каждая запись является элементом Z2, поле целых чисел по модулю 2. Андерсон и Фейл обнаружили, что для того, чтобы конфигурация была разрешимой (получение нулевого вектора из исходной конфигурации), она должна быть ортогональна двум векторам N1 и н2 ниже (изображен как массив 5 × 5, но не путать с матрицами).
Кроме того, они обнаружили, что N1 и н2 можно использовать, чтобы найти три дополнительных решения для решения, и что эти четыре решения являются единственными четырьмя решениями (за исключением избыточных перемещений) для исходной данной конфигурации. Эти четыре решения - X, X + N1, X + N2, и X + N1 + N2 где X - решение исходной данной конфигурации.[5] Введение в этот метод было опубликовано Робертом Эйзеле.[6]
Легкая погоня
«Легкая погоня» - это метод, похожий на Гауссово исключение который всегда решает загадку (если решение существует), хотя и с возможностью множества повторных шагов.[2][5][7] В этом подходе строки обрабатываются по одной, начиная с верхней строки. Все источники света в строке отключаются путем переключения соседних источников света в строке непосредственно под ним. Затем тот же метод применяется к последовательным строкам вплоть до последней. Последний ряд решается отдельно, в зависимости от его активных огней. Соответствующие индикаторы (см. Таблицу ниже) в верхней строке переключаются, и снова запускается первоначальный алгоритм, что приводит к решению.[7]
| Нижняя строка | Переключиться на верхнюю строку |
|---|---|
| ⬜⬜⬜⬛⬛ | ⬛▣⬛⬛⬛ |
| ⬜⬜⬛⬜⬜ | ⬛⬛▣⬛⬛ |
| ⬜⬛⬜⬜⬛ | ⬛⬛⬛⬛▣ |
| ⬜⬛⬛⬛⬜ | ▣▣⬛⬛⬛ |
| ⬛⬜⬜⬛⬜ | ▣⬛⬛⬛⬛ |
| ⬛⬜⬛⬜⬛ | ▣⬛⬛▣⬛ |
| ⬛⬛⬜⬜⬜ | ⬛⬛⬛▣⬛ |
Таблицы и стратегии для других размеров доски генерируются в процессе игры. Отбой с пустой доской и наблюдая за результатом переноса определенного источника света из верхнего ряда вниз в нижний ряд.
Дальнейшие результаты
После того, как единственное решение найдено, решение с минимальным числом ходов может быть определено путем исключения избыточных наборов нажатий кнопок, которые не имеют кумулятивного эффекта.[5][7] Если головоломка 5 × 5 неразрешима при легальном создании игры, два крайних левых индикатора в нижнем ряду останутся включенными, когда все остальные индикаторы будут выключены.
Существование решений доказано для самых разных конфигураций плат, таких как гексагональная,[8] в то время как решения для досок n × n для n≤200 были явно построены.[9]
Решение существует для любого случая N × N. Он разрешим на любом неориентированном графе, где щелчок по одной вершине переворачивает ее значение и ее соседи. В более общем смысле, если матрица действий симметрична, то ее диагональ всегда разрешима.[10]
Смотрите также
Рекомендации
- ^ а б c d 'Beyond Tetris' - погаснет, Тони Дельгадо, GameSetWatch, 29 января 2007 г. Доступ онлайн 18 октября 2007 г.
- ^ а б c Отбой, Страница головоломок Яапа. Доступ онлайн 18 октября 2007 г.
- ^ «Архив интересного кода». www.keithschwarz.com. Получено 2020-06-12.
- ^ а б Вайсштейн, Эрик В. "Загадка потухшего света". MathWorld.
- ^ а б c d Марлоу Андерсон, Тодд Фейл (1998). "Как выключить свет с помощью линейной алгебры" (PDF). Математический журнал. 71 (4): 300–303. Дои:10.1080 / 0025570X.1998.11996658. Архивировано из оригинал (PDF) 15 августа 2014 г.
- ^ Эйзеле, Роберт (30.07.2018). «Решение LightsOut с использованием линейной алгебры». Получено 2018-07-30. Журнал Cite требует
| журнал =(помощь) - ^ а б c Решение проблем с выключением света, Мэтью Бейкер.
- ^ unknown (20 ноября 2010 г.). «Игра с подсветкой на гексагональной сетке». Получено 30 ноября 2010.
- ^ Джим Фаулер (21 июля 2008 г.). "Решения для выключения света". Блог Джима Фаулера. Получено 30 ноября 2010.
- ^ Игорь Миневич (2012). «Симметричные матрицы над F_2 и проблема отключения света». arXiv:1206.2973 [math.RA ].