Загорайся (головоломка) - Light Up (puzzle)

Умеренно сложно Загораться головоломка (решение )

Загораться (Японский: 美術館 бидзюцукан, картинная галерея), также называемый Акари, является двоичным определением логическая головоломка опубликовано Николи. По состоянию на 2011 год три книги, полностью состоящие из Загораться пазлы были опубликованы Николи.

Правила

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

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

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

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

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

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

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

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

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

Смотрите также

• Список типов головоломок Николи
• Категория: Логические головоломки

Рекомендации

внешняя ссылка

• Английская страница Николи на Загораться