Нурикабе (головоломка) - Википедия - Nurikabe (puzzle)

Пример средней сложности 10х9 Нурикабе головоломка

Нурикабе (хирагана: ぬりかべ) является двоичным пазл решимости назван в честь Нурикабе, невидимая стена в Японский фольклор это блокирует дороги и задерживает пешие прогулки. Нурикабе, по-видимому, был изобретен и назван Николи; другие названия (и попытки локализации) головоломки включают Структура клетки и острова в потоке.

Правила

В головоломке обычно используется прямоугольная сетка ячеек, некоторые из которых содержат числа. Изначально клетки имеют неизвестный цвет, но могут быть только черными или белыми. Две клетки одного цвета считаются «связанными», если они смежны по вертикали или горизонтали, но не по диагонали. Связанные белые клетки образуют «острова», а связанные черные клетки образуют «море».

Задача состоит в том, чтобы закрасить каждую ячейку в черный или белый цвет при соблюдении следующих правил:

Каждая пронумерованная ячейка представляет собой ячейку острова, число в ней - количество ячеек на этом острове.
На каждом острове должна быть ровно одна пронумерованная ячейка.
Должно быть только одно море, которое не может содержать «лужи», т.е. области 2 × 2 черных ячеек.

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

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

История

Нурикабе был впервые разработан «ренином (れーにん)», чей псевдоним является японским произношением «Ленин» и чей автоним может быть прочитан как таковой, в 33-м выпуске (Puzzle Communication) Николи в марте 1991 года. Вскоре он произвел фурор и появлялся во всех номерах этого издания с 38-го по настоящее время.

По состоянию на 2005 год семь книг, полностью состоящих из Нурикабе пазлы были опубликованы Николи.

(Этот абзац в основном зависит от «Полного собрания интересных головоломок Николи (ニコリオモロパズル大全集)». https://web.archive.org/web/20060707011243/http://www.nikoli.co.jp/storage/addition/omopadaizen/ )

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

Решение приведенного выше примера головоломки

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

Самая большая ошибка начинающих решателей состоит в том, что они сосредотачиваются исключительно на определении черного или белого, а не другого; наиболее Нурикабе головоломки требуют перехода вперед и назад. Маркировка белых клеток может привести к тому, что другие клетки станут черными, чтобы часть черного не была изолирована, и наоборот. (Те, кто знаком с Идти можно думать о неопределенных ячейках рядом с различными регионами как о «свободах» и применять »Atari «логика для определения того, как они должны расти.)

Базовая стратегия

Человек решает головоломку Нурикабе. Точки представляют клетки, которые известны как белые.

Поскольку два острова могут касаться только углов, ячейки между двумя частичными островами (числа и соседние белые ячейки, которые еще не суммируют свои числа) должны быть черными. Часто это способ начать Нурикабе головоломки, пометив клетки, примыкающие к двум или более числам, черным.
Когда остров «готов», то есть на нем есть все белые клетки, необходимые для его количества, все клетки, которые имеют с ним одну сторону, должны быть черными. Очевидно, что любые ячейки, отмеченные цифрой «1» вначале, представляют собой целые островки, и их можно изолировать черным в начале.
Каждый раз, когда три черные ячейки образуют «локоть» - L-образную форму, - ячейка в изгибе (по диагонали от угла L) должна быть белой. (Альтернативой является «пул», за неимением лучшего термина.)
Все черные клетки в конечном итоге должны быть подключены. Если есть черная область с только одним возможным способом подключения к остальной части платы, единственный соединительный путь должен быть черным.
- Следствие: не может быть непрерывного пути с использованием вертикальных, горизонтальных или диагональных шагов из белых ячеек от одной ячейки, лежащей на краю доски, к другой такой ячейке, которая охватывает некоторые черные ячейки внутри, потому что в противном случае черные ячейки ячейки не будут подключены.
Все белые клетки в конечном итоге должны быть частью ровно одного острова. Если есть белая область, которая не содержит числа, и есть только один возможный способ подключения к пронумерованной белой области, единственный соединительный путь должен быть белым.
Некоторые головоломки потребуют расположения «недостижимых» - ячеек, которые не могут быть соединены ни с каким числом, поскольку они находятся либо слишком далеко от всех из них, либо заблокированы другими числами. Такие клетки должны быть черными. Часто эти клетки будут иметь только один путь соединения с другими черными клетками или будут образовывать локоть, требующаяся белая клетка которого (см. Предыдущий пункт) может достигать только одного числа, обеспечивая дальнейший прогресс.

Продвинутая стратегия

Пример третьей расширенной стратегии Клетка по диагонали между двумя островами должна быть черной.

Если есть квадрат, состоящий из двух черных ячеек и двух неизвестных ячеек, по крайней мере одна из двух неизвестных ячеек должна оставаться белой в соответствии с правилами. Таким образом, если одна из этих двух неизвестных ячеек (назовите ее 'A') может быть соединена с пронумерованным квадратом только через другую (назовите ее 'B'), то B обязательно должна быть белой (и A может или может не быть белым).
Если на острове размера N уже идентифицировано N-1 белых ячеек, и есть только две оставшиеся ячейки, из которых можно выбрать, и эти две ячейки соприкасаются своими углами, тогда ячейка между этими двумя, которая находится на дальней стороне острова. должен быть черным.
Если квадрат должен быть белым, и только два острова могут соединиться с ним и не иметь неопознанных ячеек, оставшихся после соединения, то если острова соединяются под углом 90 градусов (например: один остров может соединяться с верхней стороной, а другой - с правой сторона) ячейка внутри угла (та, которая касается верхнего левого угла белого квадрата в предыдущем примере) должна быть черной, чтобы избежать соединения двух островов.
Неопределенные ячейки, прилегающие к прямому ряду (или прямому столбцу) черных ячеек, могут быть проверены на то, что они черные, потому что, если они черные, они образуют два локтя, и будут две соседние белые ячейки, которые должны быть доступны с островов. . Если они не могут быть выполнены в рамках ограничений, это означает, что ячейка, проверенная на черноту, должна быть белой.

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

это НП-полный решить Нурикабе, даже если задействованы только числа 1 и 2.

Далее рассмотрим эти два правила Нурикабе:

Черные клетки образуют связанную область
Черные клетки не могут образовывать квадраты 2 × 2,

Любой из них можно игнорировать, что дает всего три варианта. Оказывается, все они NP-полны.^[1]

Связанные головоломки

Пример 7x8 Мочикоро головоломка.

Решение предыдущей головоломки.

Головоломки бинарного определения LITS и Мочикоро, также опубликовано Николи, похожи на Нурикабе и использовать аналогичные методы решения. Загадка бинарного определения Ацумари похоже на Нурикабе но основан на шестиугольной мозаике, а не на квадратной.

Мочикоро - это вариант головоломки Нурикабе:

Каждая пронумерованная ячейка принадлежит белой области, число указывает, сколько ячеек принадлежит белой области. Некоторые белые области могут не включать пронумерованные ячейки.
Все белые области должны быть соединены по диагонали.
Черная ячейка не должна занимать площадь 2x2 ячейки или больше.