Масю (ま し ゅ, Mashu , IPA [maɕu͍]; переводится как «злое влияние» [1] ) - это тип логической головоломки, разработанный и опубликованный Николи . Целью его создания было представить головоломку, в которой не используются цифры или буквы, но сохраняются глубина и эстетика.
Правила [ править ]
Масю играется на прямоугольной сетке квадратов, некоторые из которых содержат круги; каждый кружок либо «белый» (пустой), либо «черный» (залитый). Цель состоит в том, чтобы нарисовать одну непрерывную непересекающуюся петлю, которая должным образом проходит через все обведенные кружки. Петля должна «входить» в каждую ячейку, через которую она проходит, из центра одной из своих четырех сторон и «выходить» с другой стороны; поэтому все повороты составляют 90 градусов . [1]
У двух разновидностей круга разные требования к тому, как петля должна проходить через них:
- Белые круги должны проходить насквозь, но петля должна поворачиваться в предыдущей и / или следующей ячейке на своем пути.
- Черные круги должны быть включены, но петля должна проходить прямо через следующую и предыдущую ячейки на своем пути.
Варианты [ править ]
- Есть дополнительно или только серые кружки. Решающая программа должна определить, какие из этих серых кружков белые, а какие черные.
- Схема представляет собой тороид ; т.е. левый и правый края диаграммы, а также верхний и нижний края диаграммы склеиваются.
- Диаграмма разделена на регионы; петля должна повернуться в каждом регионе хотя бы один раз.
- Диаграмма воспроизводится на гексагональной сетке, где серые круги обозначают повороты на 60 градусов, где петля поворачивается как до, так и после поворота, и черные круги, обозначающие повороты на 120 градусов, где петля идет прямо по ячейкам до и после поворота.
История [ править ]
Ранняя версия Масю впервые появилась в Puzzle Communication Nikoli # 84 под названием Shinju no Kubikazari (真珠 の 首飾 り, что означает «жемчужное ожерелье»). Эта головоломка состоит только из белых кругов. Черные круги были введены в Puzzle Communication Nikoli # 90, а головоломка была переименована в Shiroshinju Kuroshinju (白 真珠 黒 真珠, что означает «белый жемчуг и черный жемчуг»). Это улучшение углубило головоломку и сделало ее популярной. Масю , который изначально неверно истолковал президентом Николи кандзи真珠 ( синдзю ) и, по-видимому, стал шуткой в офисе Николи, был принят в Puzzle Communication Nikoli. # 103 на замену старому длинному имени.
Способы решения [ править ]
Понимание нюансов кругов и того, как они взаимодействуют друг с другом, является ключом к решению головоломки Масю . Вообще говоря, проще всего начать с внешней границы сетки и работать внутрь. Вот несколько основных сценариев, в которых можно определить части цикла:
- Любой сегмент, идущий от черного круга, должен пройти две ячейки в этом направлении, не пересекая другую часть цикла или внешнюю границу; в каждой черной клетке должно быть два таких сегмента под прямым углом. Логическая комбинация этих двух утверждений состоит в том, что если сегмент из черной ячейки не может быть нарисован в некотором ортогональном направлении, должен быть нарисован сегмент в противоположном направлении . Например, если по закону нельзя пройти на две клетки вверх от черного круга, то петля должна пройти вниз от этого черного круга на две клетки. Это дает два общих результата:
- Любой черный круг вдоль внешней границы или одна ячейка от внешней границы должен иметь сегмент, ведущий от границы (а те, кто находится достаточно близко к углу, должны отходить от обеих стен, определяя путь петли через круг);
- Ортогонально смежные черные круги должны иметь сегменты, расходящиеся друг от друга.
- Черные круги, расположенные перпендикулярно концу петли, которая не движется к нему, должны иметь петлю, направленную от другого сегмента петли.
- Белые круги вдоль внешней границы, очевидно, нуждаются в петле, чтобы пройти через них параллельно границе; если два белых кружка вдоль границы смежны или находятся на расстоянии одной ячейки друг от друга, тогда петлю нужно будет повернуть в сторону от границы сразу за кружками.
- Если три или более белых круга являются смежными и коллинеарными ортогонально, тогда цикл должен будет пройти через каждый из этих кругов перпендикулярно линии кругов.
- Если два белых круга смежны перпендикулярно и ячейка на каждом конце имеет сегмент петли, входящий параллельно линии кругов, тогда петля должна будет пройти через каждый из этих кругов перпендикулярно их линии. (В противном случае линия, проходящая через них, соединится с соседним сегментом, и одна из белых ячеек не будет рядом с поворотом в петле.)
- Черный круг с двумя белыми кругами, расположенными по диагонали на одной стороне, должен иметь петлю, уходящую с этой стороны. Если нет, и вместо этого он проходит между белыми кругами, тогда белые круги будут параллельны этому участку петли и сделать невозможным завершение черного круга.
- Черные круги с тремя соседними по диагонали белыми кругами могут быть полностью заполнены этим правилом.
- Если диаграмму разрезать виртуально на две части, петля должна пересекать линию разреза четное количество раз. Это связано с теоремой Жордана о кривой .
Как и в других головоломках с построением петель, «коротких замыканий» также необходимо избегать: поскольку решение должно состоять из одного цикла, любой сегмент, который мог бы замкнуть цикл, запрещен, если он не дает немедленного решения всей головоломки.
Как и многие другие комбинаторные и логические головоломки, Масю бывает очень сложно решить; решение Масю на сколь угодно больших сетках является NP-полной задачей. [2] Однако опубликованные примеры головоломок обычно строятся таким образом, что их можно решить в разумные сроки.
См. Также [ править ]
Ссылки [ править ]
Внешние ссылки [ править ]
