Light Up ( яп . Bijutsukan , художественная галерея), также называемая Акари , представляет собой логическую головоломку с двоичным определением, опубликованную Николи . По состоянию на 2011 год Nikoli опубликовал три книги, полностью состоящие из загадок Light Up .
Правила
Light Up играется на прямоугольной сетке из белых и черных ячеек. Игрок помещает лампочки в белые ячейки так, чтобы никакие две лампочки не светили друг на друга, пока не загорится вся сетка. Лампочка излучает лучи света по горизонтали и вертикали, освещая весь свой ряд и столбец, если только ее свет не блокируется черной клеткой. На черной ячейке может быть число от 0 до 4, указывающее, сколько лампочек должно быть размещено рядом с ее четырьмя сторонами; например, ячейка с цифрой 4 должна иметь четыре лампочки вокруг нее, по одной с каждой стороны, а ячейка с цифрой 0 не может иметь лампочку рядом с любой из ее сторон. Ненумерованная черная ячейка может иметь любое количество лампочек рядом или ни одной. Луковицы, расположенные по диагонали рядом с пронумерованной ячейкой, не влияют на подсчет луковиц.
Методы решения
Типичная отправная точка в решении загадки Light Up - найти черную ячейку с 4 или ячейку с меньшим номером, которая заблокирована с одной или нескольких сторон (например, 3 у стены или 2 дюйма угол) и, следовательно, имеет только одну конфигурацию окружающих лампочек. После этого шага другие пронумерованные ячейки могут быть освещены с одной или нескольких сторон, сужая возможные конфигурации ламп вокруг них и в некоторых случаях делая возможной только одну конфигурацию.
Другой распространенный метод - найти ячейку, которая еще не горит, и определить, есть ли только одна возможная ячейка, в которую можно поместить лампочку, чтобы зажечь ее.
Когда неясно, где разместить лампочку, можно также разместить точки в белых клетках, у которых не может быть лампочек, например, около 0 или в местах, где лампочка создала бы противоречие. Например, электрическая лампочка, расположенная по диагонали рядом с 3, будет блокировать две из окружающих ее ячеек, делая невозможным наличие трех лампочек вокруг нее; поэтому диагональные ячейки вокруг цифры 3 никогда не могут быть освещены и всегда могут быть пунктирными. Точно так же можно поставить точки в тех местах, где лампочка может «замочить» другую незажженную ячейку, делая невозможным ее зажечь без нарушения правил.
Более продвинутые техники, как правило, сосредоточены на различных комбинациях подсказок. Две тройки, которые находятся на расстоянии одного пробела друг от друга, например, без ничего между ними или двумя другими сторонами ячейки между ними, должны иметь лампочку в этом месте, а два пробела рядом с двумя тройками на линии, соединяющей их. . Если нет, то есть две лампочки, освещающие друг друга. Кроме того, исходя из этого вывода, оставшиеся четыре клетки, окружающие тройки, должны содержать две лампочки. Обратите внимание: поскольку четыре пробела расположены в два ряда, между которыми ничего нет, в каждой строке должна быть по одной лампочке, чтобы можно было пометить все остальные пробелы в этих рядах как пустые.
Другой довольно распространенный образец - это 1, по диагонали рядом с 2, с одним из пространств рядом с 2, но не рядом с 1, либо пустым, либо обнесенным стеной. Максимум одна лампочка может быть помещена в две ячейки, общие для двух ключей, поэтому последняя лампочка должна находиться в последнем пространстве вокруг 2. Теперь известно, что в этих ячейках ровно одна лампочка, поэтому другие ячейки рядом с 1 оба должны быть пустыми.
Вычислительная сложность
Определение того, разрешима ли данная загадка Light Up, является NP-полной . [1] Это доказано полиномиальным сокращением от Circuit-SAT , которое, как известно, является NP-полным, до загадок Light Up.
Смотрите также
- Список типов головоломок Николи
- Категория: Логические головоломки
Рекомендации
- ^ Макфейл, Brandon (28 февраля 2005). «Light Up NP-завершен» (PDF) .