Логическая головоломка "Освети галерею" (Логическая головоломка "Музей")

Введение

Логическая головоломка Light Up, изданная компанией Nikoli.

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

Правила

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

Методы растворения

Типичная отправная точка в решении головоломки Light Up — найти чёрную ячейку с числом 4 или ячейку с меньшим числом, которая заблокирована с одной или нескольких сторон (например, 3 у стены или 2 в углу) и, следовательно, имеет только одну возможную конфигурацию окружающих лампочек. После этого шага другие пронумерованные ячейки могут быть освещены с одной или нескольких сторон, сужая возможные конфигурации лампочек вокруг них и, в некоторых случаях, оставляя только одну возможную конфигурацию. Другой распространённый приём — искать ячейку, которая ещё не освещена, и определить, есть ли только одна возможная ячейка, в которую можно поместить лампочку, чтобы её осветить. Если неясно, куда поместить лампочку, можно также ставить точки в белые ячейки, в которых лампочка не может быть установлена, например, вокруг 0 или в местах, где лампочка приведёт к противоречию. Например, лампочка, расположенная по диагонали рядом с 3, блокирует две окружающие её ячейки, делая невозможным размещение трёх лампочек вокруг неё; следовательно, диагональные ячейки вокруг 3 никогда не могут быть освещены и всегда могут быть отмечены точками. Аналогично, можно ставить точки в местах, где лампочка «загонит в угол» другую неосвещённую ячейку, делая невозможным её освещение без нарушения правил. Более продвинутые техники обычно сосредоточены на различных комбинациях подсказок. Например, две 3, расположенные на расстоянии одного шага друг от друга, при отсутствии ячеек между ними или по другим двум сторонам промежуточной ячейки, должны иметь лампочку в этой промежуточной ячейке, а также по одной лампочке в двух ячейках, соседних с обеими 3, на линии, соединяющей их. В противном случае получится, что две лампочки освещают друг друга. Кроме того, из этого следует, что оставшиеся четыре ячейки, окружающие обе 3, должны содержать две лампочки. Обратите внимание, что поскольку эти четыре ячейки расположены в два ряда без промежутков, в каждом ряду должна быть одна лампочка, поэтому все остальные ячейки в этих рядах можно пометить как пустые. Другой довольно распространённый шаблон — 1, расположенная по диагонали к 2, при этом одна из ячеек, соседних с 2, но не соседних с 1, либо пуста, либо заблокирована стеной. В двух ячейках, общих для обеих подсказок, можно разместить не более одной лампочки, поэтому последняя лампочка должна быть помещена в последнюю свободную ячейку вокруг 2. Теперь известно, что в этих ячейках находится ровно одна лампочка, поэтому остальные ячейки, соседние с 1, должны быть пустыми.

A typical starting point in the solution of a Light Up puzzle is to find a black cell with a 4, or a cell with a smaller number that is blocked on one or more sides (for example, a 3 against a wall or a 2 in a corner) and therefore has only one configuration of surrounding bulbs. After this step, other numbered cells may be illuminated on one or more sides, narrowing down the possible bulb configurations around them, and in some cases making only one configuration possible. Another common technique is to look for a cell that is not yet lit, and determine if there is only one possible cell in which a bulb can be placed to light it up. When it is unclear where to place a bulb, one may also place dots in white cells that cannot have bulbs, such as around a 0 or in places where a bulb would create a contradiction. For example, a light bulb placed diagonally adjacent to a 3 will block two of its surrounding cells, making it impossible to have three bulbs around it; therefore, the diagonal cells around a 3 can never have lights in them and can be always dotted. Similarly, one may put dots in places where a bulb would "trap" another unlit cell, making it impossible to light it up without breaking the rules. More advanced techniques tend to focus on different combinations of clues. Two 3s that are one space apart, for example, with nothing between them or to the other two sides of the cell in between, must have a lightbulb in that space, and the two spaces next to the two threes, on the line joining them. If not, then one would have two lightbulbs illuminating each other. Also, from this deduction, the remaining four cells surrounding the threes must contain two lightbulbs. Note that as the four spaces are arranged in two rows with nothing in between, one must have one lightbulb to each row, so one can mark all other spaces in those rows as empty. Another fairly common pattern is a 1 diagonally adjacent to a 2, with one of the spaces next to the 2 but not adjacent to the 1 either empty or walled off. At most one lightbulb can be placed in the two cells common to the two clues, so the last lightbulb must go in the last space around the 2. Now, it is known that there is exactly one lightbulb in those cells, so the other cells next to the 1 must both be empty.

Комплексность вычислений

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