Зажги (головоломка)

Головоломка средней сложности *с подсветкой* ( решение )

Light Up ( яп . 美術館 bijutsukan , художественная галерея), также называемая Акари с двоичным определением, (明かり, свет) — логическая головоломка опубликованная Николи . три книги, полностью состоящие из головоломок Light Up По состоянию на 2011 год Николи опубликовал .

Правила

В Light Up используется прямоугольная сетка из белых и черных ячеек. Игрок размещает лампочки в белых клетках так, чтобы никакие две лампочки не светили друг на друга, пока не загорится вся сетка. Лампа излучает лучи света по горизонтали и вертикали, освещая весь ее ряд и столбец, если только ее свет не блокируется черной ячейкой. На черной клетке может быть число от 0 до 4, обозначающее, сколько лампочек необходимо разместить рядом с ее четырьмя сторонами; например, клетка с цифрой 4 должна иметь вокруг себя четыре лампочки, по одной с каждой стороны, а клетка с цифрой 0 не может иметь лампочку рядом ни с одной из сторон. Ненумерованная черная клетка может иметь любое количество соседних с ней лампочек или ни одной. Лампочки, расположенные по диагонали рядом с пронумерованной ячейкой, не учитываются при подсчете лампочек.

Методы решения

Типичная отправная точка в решении головоломки Light Up — найти черную клетку с цифрой 4 или клетку с меньшим числом, заблокированную с одной или нескольких сторон (например, 3 у стены или 2 в угол) и поэтому имеет только одну конфигурацию окружающих лампочек. После этого шага другие пронумерованные ячейки могут быть освещены с одной или нескольких сторон, что сужает возможные конфигурации лампочек вокруг них и в некоторых случаях делает возможной только одну конфигурацию.

Другой распространенный метод — найти ячейку, которая еще не освещена, и определить, существует ли только одна возможная ячейка, в которую можно поместить лампочку, чтобы ее осветить.

Если неясно, где разместить лампочку, можно также разместить точки в белых клетках, в которых не может быть лампочек, например, вокруг 0 или в тех местах, где лампочка могла бы создать противоречие. Например, лампочка, расположенная по диагонали рядом с цифрой 3, заблокирует две окружающие ее ячейки, что сделает невозможным размещение вокруг нее трех лампочек; следовательно, диагональные ячейки вокруг цифры 3 никогда не могут иметь светящихся элементов и всегда могут быть расставлены точками. Точно так же можно поставить точки в тех местах, где лампочка «заманивает» в ловушку другую неосвещенную клетку, делая невозможным ее освещение, не нарушая правил.

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

Другой довольно распространенный шаблон — это цифра 1, примыкающая по диагонали к цифре 2, причем одно из мест рядом с цифрой 2, но не смежное с цифрой 1, либо пусто, либо отгорожено стеной. В две ячейки, общие для двух подсказок, можно поместить не более одной лампочки, поэтому последняя лампочка должна находиться в последнем пространстве вокруг 2. Теперь известно, что в этих ячейках находится ровно одна лампочка, поэтому остальные ячейки оба рядом с 1 должны быть пустыми.

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

Вычислительная сложность

Определение того, разрешима ли данная головоломка с подсветкой, является NP-полным . ^[1] Это доказывается полиномиальным сокращением времени от Circuit-SAT , который, как известно, является NP-полным, к головоломкам Light Up.

Вариации оригинальной головоломки Light Up, в которой есть стены без номеров плюс стены с одним определенным числом, то есть 0, 1, 2, 3 или 4 (мы называем эти варианты Акари- $n$ ), также были исследованы на предмет сложности. Путем полиномиального сокращения времени из Circuit-SAT показано, что Акари-1, Акари-2 и Акари-3 являются NP-полными; для Акари-4 и головоломок без цифр показано, что они находятся в P; Акари-0 пока не классифицирован. ^[2]

См. также

Ссылки

^ Макфейл, Брэндон (28 февраля 2005 г.). «Light Up является NP-полным» (PDF) .
^ Пуллес, Брэм (9 января 2021 г.). «Анализ Акари» (PDF) . Проверено 27 мая 2021 г.

Внешние ссылки

Английская страница Николи на Light Up

[1] Макфейл, Брэндон (28 февраля 2005 г.). «Light Up является NP-полным» (PDF) .

[2] Пуллес, Брэм (9 января 2021 г.). «Анализ Акари» (PDF) . Проверено 27 мая 2021 г.

[1]

[2]