Пример головоломки Nurikabe средней сложности 10x9
Nurikabe ( хирагана : ぬりかべ) — головоломка на бинарное определение, названная в честь Nurikabe, невидимой стены в японском фольклоре , которая блокирует дороги и задерживает пешеходное движение. Nurikabe, по-видимому, был придуман и назван издателем Nikoli ; другие названия (и попытки локализации) для головоломки включают Cell Structure и Islands in the Stream .
Правила
Головоломка играется на типичной прямоугольной сетке ячеек, некоторые из которых содержат числа. Ячейки изначально неизвестного цвета, но могут быть только черными или белыми. Две ячейки одного цвета считаются «связанными», если они соседствуют по вертикали или горизонтали, но не по диагонали. Соединенные белые ячейки образуют «острова», а соединенные черные ячейки образуют «море».
Задача состоит в том, чтобы закрасить каждую клетку в черный или белый цвет, соблюдая следующие правила:
Каждая пронумерованная ячейка — это ячейка острова, число в ней — это количество ячеек на этом острове.
Каждый остров должен содержать ровно одну пронумерованную ячейку.
Должно быть только одно море, в котором не должно быть «бассейнов», т. е. областей 2×2 черных клеток.
Люди, решающие задачу, обычно отмечают точками непронумерованные ячейки, которые они определили как принадлежащие острову.
Как и в большинстве других головоломок на чистую логику , ожидается единственное решение, и сетка, содержащая случайные числа, вряд ли обеспечит единственно решаемую головоломку Нурикабэ .
История
Нурикабэ впервые было разработано «ренином» (れーにん), чей псевдоним является японским произношением слова «Ленин» и чье самоназвание можно прочитать именно так, в 33-м выпуске (Puzzle Communication) Nikoli в марте 1991 года. Вскоре оно произвело сенсацию и появлялось во всех выпусках этого издания с 38-го по настоящее время.
По состоянию на 2005 год Николи опубликовал семь книг, полностью состоящих из головоломок Нурикабэ . [1]
Методы решения
Решение примера головоломки, приведенного выше
Для решения головоломки Нурикабэ не требуется слепого угадывания . Вместо этого можно разработать и следовать ряду простых процедур и правил, предполагая, что решатель достаточно наблюдателен, чтобы найти, где их применить.
Самая большая ошибка начинающих решателей — сосредоточиться исключительно на определении черного или белого, а не другого; большинство головоломок Nurikabe требуют движения вперед и назад. Отметка белых клеток может заставить другие клетки стать черными, чтобы не изолировать часть черного, и наоборот. (Те, кто знаком с Go, могут думать о неопределенных клетках рядом с различными областями как о «свободах» и применять логику « атари », чтобы определить, как они должны расти.)
Основная стратегия
Головоломка Нурикабе, решаемая человеком. Точки представляют собой клетки, которые, как известно, белые.
Поскольку два острова могут соприкасаться только углами, клетки между двумя частичными островами (числа и соседние белые клетки, которые еще не суммируют свои числа) должны быть черными. Это часто является способом начать головоломку Нурикабэ , помечая клетки, соседствующие с двумя или более числами, как черные.
Как только остров "завершен" — то есть, у него есть все белые клетки, требуемые его номером — все клетки, которые делят с ним сторону, должны быть черными. Очевидно, что любые клетки, помеченные "1" в начале, являются завершенными островами сами по себе и могут быть изолированы черным цветом в начале.
Всякий раз, когда три черных клетки образуют «локоть» — L-образную форму — клетка в изгибе (по диагонали от угла L) должна быть белой. (Альтернативой является «бассейн», за неимением лучшего термина.)
Все черные клетки в конечном итоге должны быть соединены. Если есть черная область с единственным возможным способом соединения с остальной частью доски, единственный соединительный путь должен быть черным.
Следствие: не может быть непрерывного пути, использующего вертикальные, горизонтальные или диагональные шаги из белых клеток от одной клетки, лежащей на краю доски, до другой такой же клетки, которая заключает в себе некоторые черные клетки, потому что в противном случае черные клетки не будут связаны.
Все белые клетки в конечном итоге должны быть частью ровно одного острова. Если есть белая область, которая не содержит числа, и есть только один возможный способ для нее соединиться с пронумерованной белой областью, единственный соединительный путь должен быть белым.
Некоторые головоломки потребуют расположения «недостижимых» ячеек — ячеек, которые не могут быть соединены ни с одним числом, находясь слишком далеко от всех них или заблокированные другими числами. Такие ячейки должны быть черными. Часто эти ячейки будут иметь только один путь соединения с другими черными ячейками или будут образовывать локоть, требуемая белая ячейка которого (см. предыдущий пункт) может достичь только одного числа, позволяя дальнейшее продвижение.
Расширенная стратегия
Пример третьей продвинутой стратегии. Клетка по диагонали между двумя островами должна быть черной.
Если есть квадрат, состоящий из двух черных клеток и двух неизвестных клеток, то по правилам хотя бы одна из двух неизвестных клеток должна остаться белой. Таким образом, если одна из этих двух неизвестных клеток (назовем ее «A») может быть соединена с пронумерованным квадратом только посредством другой (назовем ее «B»), то B обязательно должна быть белой (а A может быть или не быть белой).
Если на острове размером N уже идентифицировано N-1 белых клеток, и осталось выбрать только две клетки, и эти две клетки соприкасаются своими углами, то клетка между этими двумя, которая находится на дальней стороне острова, должна быть черной.
Если квадрат должен быть белым и с ним могут соединяться только два острова, и после соединения не должно остаться неопознанных клеток, то если острова соединяются под углом 90 градусов (например, один остров может соединяться с верхней стороной, а другой — с правой стороной), то клетка внутри угла (та, которая касается верхнего левого угла белого квадрата в предыдущем примере) должна быть черной, чтобы избежать соединения двух островов.
Неопределенные ячейки, соседствующие с прямой строкой (или прямой колонной) черных ячеек, можно проверить на предмет черного цвета, поскольку если они черные, то это сформирует два локтя, и будут две соседние белые ячейки, которые должны быть доступны с островов. Если они не могут быть выполнены в рамках ограничений, это означает, что ячейка, которая была проверена на предмет черного цвета, должна быть белой.
Сложность вычислений
Решение задачи Нурикабэ является NP-полной задачей , даже если в ней участвуют только числа 1 и 2.
Далее рассмотрим два правила Нурикабэ:
Черные клетки образуют связанную область
Черные клетки не могут образовывать квадраты 2 × 2,
Любой из них можно проигнорировать, что даст в общей сложности три варианта. Как оказалось, все они NP-полные. [2]
Похожие головоломки
Пример головоломки Мотикоро 8х8.Решение предыдущей головоломки.
Головоломки бинарного определения LITS и Mochikoro, также опубликованные Николи , похожи на Нурикабэ и используют похожие методы решения. Головоломка бинарного определения Atsumari похожа на Нурикабэ, но основана на шестиугольной, а не квадратной мозаике.
Мотикоро — это вариант головоломки Нурикабэ:
Каждая пронумерованная ячейка принадлежит белой области, число указывает, сколько ячеек принадлежит белой области. Некоторые белые области могут не включать пронумерованную ячейку.
Все белые области должны быть соединены по диагонали.
Черная клетка не должна покрывать площадь 2х2 клетки или больше.
^ Этот абзац в основном зависит от «Полного собрания интересных головоломок Николи (ニコリ オモロパズル大全集)». https://web.archive.org/web/20060707011243/http://www.nikoli.co.jp/storage/addition/omopadaizen/
^ Хольцер, Маркус; Кляйн, Андреас; Кутриб, Мартин (2004). «О NP-полноте головоломки-карандаша NURIKABE и ее вариантах» (PDF) . Труды 3-й Международной конференции по развлечениям с алгоритмами . S2CID 16082806. Архивировано из оригинала (PDF) 2020-02-11.
Брэндон МакФайл, Джеймс Д. Фикс. Нурикабе — NP-полная северо-западная конференция CSCC, 2004. Также представлен на коллоквиуме Reed Mathematics, 2004.
Маркус Хольцер, Андреас Кляйн и Мартин Кутриб. О NP-полноте головоломки-карандаша NURIKABE и ее разновидностях. Труды 3-й международной конференции по развлечениям с алгоритмами, 2004.
