Нурикабэ (головоломка)

Эта статья о головоломке. Чтобы узнать о японском духе, см. Нурикабэ (фольклор) .

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

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

Правила

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

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

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

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

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

История

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример головоломки Мотикоро 8х8.

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

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

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

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

См. также

• Тральщик
• Хасивокакеро
• Список типов головоломок Николи

Ссылки

• Брэндон Макфэйл, Джеймс Д. Фикс. Нурикабе - NP-Complete NW конференция CSCC, 2004 г. Также представлен на коллоквиуме Reed Mathematics, 2004 г.
• Маркус Хольцер, Андреас Кляйн и Мартин Кутриб. О NP-полноте карандашной головоломки НУРИКАБЭ и ее вариантах . Материалы 3-й Международной конференции по развлечениям с алгоритмами , 2004 г.