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