Масю

Масю ( ましゅ , Машу , IPA [maɕu͍];) — это разновидность логической головоломки , разработанная и изданная Николи . Целью его создания было представить головоломку, в которой не используются цифры и буквы, но при этом сохраняется глубина и эстетика.

Правила

В Масю играют на прямоугольной сетке квадратов, некоторые из которых содержат круги; каждый круг либо «белый» (пустой), либо «черный» (заполненный). Цель состоит в том, чтобы нарисовать один непрерывный непересекающийся цикл, который правильно проходит через все обведенные ячейки. Цикл должен «входить» в каждую ячейку, через которую он проходит, из центра одной из четырех ее сторон и «выходить» с другой стороны; поэтому все повороты составляют 90 градусов . ^[1]

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

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

Варианты

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

История

Ранняя версия Масю впервые появилась в Puzzle Communication Nikoli #84 под названием Shinju no Kubikazari (真珠の首飾り, что означает «жемчужное ожерелье»). Эта головоломка содержит только белые круги. Черные круги были представлены в Puzzle Communication Nikoli #90, а головоломка была переименована в Сирошиндзю Куросиндзю (白真珠黒真珠, что означает «белый жемчуг и черный жемчуг»). Это улучшение углубило загадку и сделало ее популярной. Масю президентом Николи , что изначально является неправильным прочтением кандзи 真珠 ( синдзю ). ^{[ нужна ссылка ]}и, очевидно, ставший внутренней шуткой в офисе Николи, был принят в Puzzle Communication Nikoli # 103, чтобы заменить старое длинное имя.

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

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

Любой сегмент, выходящий из черного круга, должен пройти две клетки в этом направлении, не пересекая другую часть цикла или внешнюю границу; каждая черная клетка должна иметь два таких отрезка под прямым углом. Логическая комбинация этих двух утверждений заключается в том, что если сегмент черной клетки нельзя нарисовать в каком-то ортогональном направлении, сегмент в противоположном направлении необходимо нарисовать . Например, если нельзя по закону пройти на две клетки вверх от черного круга, то петля должна пройти вниз от этого черного круга на две клетки. Это имеет два общих результата:
- Любой черный круг вдоль внешней границы или одна ячейка от внешней границы должен иметь сегмент, ведущий от границы (а сегменты, расположенные достаточно близко к углу, должны вести от обеих стен, определяя путь цикла через круг);
- Ортогонально соседние черные круги должны иметь сегменты, отходящие друг от друга.
- Черные круги, расположенные ортогонально рядом с концом петли, которая не движется к нему, должны указывать на то, что петля движется в сторону от другого сегмента петли.
Белым кругам вдоль внешней границы очевидно необходимо, чтобы петля проходила через них параллельно границе; если два белых круга вдоль границы соседствуют или находятся на расстоянии одной ячейки друг от друга, то петлю нужно будет отвернуть от границы сразу за кругами.
Если три или более белых круга ортогонально смежны и коллинеарны, то петля должна будет пройти через каждый из этих кругов перпендикулярно линии кругов.
Если два белых круга ортогонально смежны и ячейка на обоих концах имеет сегмент петли, входящий параллельно линии кругов, то петля должна будет пройти через каждый из этих кругов перпендикулярно их линии. (Иначе линия, проходящая через них, соединилась бы с соседним сегментом, и одна из белых клеток не оказалась бы рядом с поворотом цикла.)
Черный круг с двумя белыми кругами, расположенными по диагонали рядом с одной и той же стороной, должен иметь петлю, направленную от этой стороны. Если нет, и вместо этого он пойдет между белыми кругами, тогда белые круги будут параллельны этой части цикла и сделают невозможным завершение черного круга.
- По этому правилу можно полностью заполнить черные круги с тремя белыми кругами, расположенными по диагонали.
Если диаграмма разрезана практически на две части, петля должна пересечь линию разреза четное число раз. Это связано с теоремой Жордана о кривой .

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

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

См. также

Список типов головоломок Николи

Ссылки

^ Кнут, Дональд (2011), «Николи предпочитает головоломки», Избранные статьи о развлечениях и играх , CSLI Publications, стр. 473–476 .
^ Фридман, Эрих (27 марта 2012 г.). «Жемчужные головоломки NP-полны» . Архивировано из оригинала 4 февраля 2012 г.

Внешние ссылки

[knuth-1] Кнут, Дональд (2011), «Николи предпочитает головоломки», Избранные статьи о развлечениях и играх , CSLI Publications, стр. 473–476 .

[Friedman-2] Фридман, Эрих (27 марта 2012 г.). «Жемчужные головоломки NP-полны» . Архивировано из оригинала 4 февраля 2012 г.

[1]

[2]