Как решать головоломки Lights Out: метод «погони за огнями» простыми словами

Lights Out это классическая головоломка на сетке, которая впервые продавалась как карманная электронная игра в 1995 году. Её правила умещаются в одно предложение, но случайное поле может показаться нерешаемым. Хорошая новость: есть простой механический метод, который решает любое поле, если у него есть решение. А когда поймёшь, почему он работает, начнёшь сам замечать короткие пути.

Правила

Перед тобой сетка огней, в классическом варианте 5×5. Одни горят, другие нет. Нажатие на огонь переключает его и четырёх соседей по сторонам (сверху, снизу, слева и справа). У огней на краю соседей просто меньше. Цель: погасить все огни.

Два факта, которые меняют всё

Прежде чем говорить о стратегии, вот два наблюдения, после которых головоломка пугает гораздо меньше:

1. Порядок не важен. Нажать A, а потом B, это ровно то же самое, что нажать B, а потом A.
2. Два нажатия отменяют друг друга. Нажми один и тот же огонь дважды, и будто ты его не трогал.

Вместе это значит, что решение не последовательность ходов. Это просто набор огней, каждый из которых нажат один раз или ни разу. Пугающий перебор превращается в задачу, над которой можно рассуждать.

Погоня за огнями, шаг за шагом

Стандартный метод называется погоней за огнями (light chasing):

1. Посмотри на верхний ряд. Для каждого горящего огня в ряду 1 нажми огонь прямо под ним в ряду 2.
2. Ряд 1 теперь полностью погас. Спустись ниже: для каждого огня, который всё ещё горит в ряду 2, нажми огонь прямо под ним в ряду 3.
3. Продолжай так, ряд за рядом, пока не дойдёшь до нижнего.

Почему это работает: нажатие в ряду 2 переключает огонь прямо над ним в ряду 1, и больше ничего в ряду 1. Значит, каждое нажатие в ряду 2 гасит ровно один огонь в ряду 1. Следующие нажатия происходят ниже, поэтому законченный ряд больше никогда не меняется.

Заметь ещё одно: как только ты решил, что нажимать (или не нажимать) в верхнем ряду, все остальные нажатия определены однозначно. Вся головоломка на самом деле сводится к верхнему ряду.

Проблема нижнего ряда

После погони все ряды гаснут, кроме, как правило, нижнего. Под ним нет ряда, который можно нажать, и ты застреваешь. Выход такой: вернуться к верхнему ряду, нажать там определённый набор огней и снова пройти погоней сверху вниз.

Какие именно огни? Это зависит только от узора, оставшегося в нижнем ряду. Для классического поля 5×5, если пронумеровать позиции от 1 до 5 слева направо:

• В нижнем ряду горят огни 1 и 5: нажми 4 и 5 в верхнем ряду
• Огни 2 и 4: нажми 2 и 5
• Огни 1, 2 и 3: нажми 2
• Огни 3, 4 и 5: нажми 4
• Огни 1, 3 и 4: нажми 5
• Огни 2, 3 и 5: нажми 1
• Огни 1, 2, 4 и 5: нажми 3

Нажми эти огни в верхнем ряду, снова пройди погоней вниз, и поле погаснет.

Если оставшегося узора нет в списке, у этого поля 5×5 нет решения. И это не редкость: решаема лишь одна из четырёх возможных расстановок 5×5. А у каждого решаемого поля 5×5 ровно четыре разных решения.

Почему таблица работает: каждое нажатие это переключение, поэтому эффекты просто складываются. Дополнительные нажатия в верхнем ряду меняют нижний ряд строго определённым образом, а список сопоставляет каждому оставшемуся узору нажатия, которые его отменяют.

Этот список подходит только для 5×5. У других размеров свой, и его можно составить самому: на погашенном поле нажми один огонь в верхнем ряду, пройди погоней вниз и запиши, что осталось в нижнем ряду. Повтори для каждой позиции верхнего ряда и комбинируй результаты.

Даёт ли погоня самое короткое решение?

Обычно нет. Погоня всегда находит решение, если оно есть, но может потратить гораздо больше нажатий, чем нужно, ведь она механически идёт по рядам и не смотрит на поле целиком.

Чтобы найти самое короткое решение, нужно сравнить возможные решения и выбрать то, где меньше нажатий. Опытные игроки ещё и учатся узнавать фигуры. Самая простая: когда горят пять огней в форме креста, одно нажатие в центре гасит их все.

Вариант на три состояния

В некоторых версиях у плиток три состояния вместо «горит» и «не горит». Каждое нажатие сдвигает плитку и её соседей на шаг по кругу: A становится B, B становится C, а C возвращается к A. Те же идеи работают и здесь, с небольшими изменениями:

• Порядок по-прежнему не важен.
• Три нажатия ничего не меняют, поэтому каждую плитку нажимают ноль, один или два раза.
• Погоня тоже работает: выбери целевое состояние. Для каждой плитки ряда 1, которая не в цели, нажми плитку под ней один или два раза, сколько нужно, чтобы довести её по кругу.
• Нижний ряд всё так же может остаться, и выход всё так же в верхнем ряду. Только теперь у каждой верхней плитки три варианта, и таблица становится больше.

Если цель просто «сделать все плитки одинаковыми», у тебя есть бонус: можно попробовать каждое целевое состояние и выбрать то, где выходит короче.

Под капотом обе версии решаются линейной алгеброй с арифметикой, которая «заворачивается» на 2 или на 3. Именно так создатели головоломок проверяют, что у уровня есть решение, и вычисляют его настоящий минимум ходов.

Furzzle: классика с собаками, кошками и кроликами

Furzzle это наша уютная версия этой классики. Вместо огней на плитках милые животные. Коснись плитки, и она вместе с четырьмя соседями превратится в следующее животное: 🐶 → 🐱 → 🐰 → 🐶. Чтобы победить, сделай всё поле одним и тем же животным, любым на твой выбор.

В первых мирах только собаки и кошки, это вариант на два состояния. Дальше появляются кролики, вариант на три состояния, а поля растут от 3×3 до 7×7. Доказано, что у каждого уровня есть решение, и для каждого известен минимум ходов, вычисленный той же математикой, что описана выше. Пройдя уровень, ты видишь свои ходы рядом с этим минимумом.

Погоня за огнями проведёт тебя через множество полей. А уложиться в минимум, вот где начинается самое интересное.

Хочешь попробовать? Сыграй в сегодняшний Furzzle дня в браузере без установки или скачай Furzzle в Google Play, чтобы открыть все миры.