Масю - Masyu

Образец головоломки
Решение загадки выше

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

Правила

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

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

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

Варианты

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

История

Ранняя версия Масю впервые появился в Пазл Общение Николи №84 под названием Синдзю-но Кубиказари (真珠 の 首飾 り, что означает «жемчужное ожерелье»). Эта головоломка состоит только из белых кругов. Черные круги были введены в Пазл Общение Николи # 90, и пазл был переименован Широшинджу Куросинджу (白 真珠 黒 真珠, что означает «белый жемчуг и черный жемчуг»). Это улучшение усугубило загадку и сделало ее популярной. Масю, что изначально неверно истолковал президент Николи кандзи 真珠 (Shinju), и, видимо, стало шуткой в ​​офисе Николи, был принят в Пазл Общение Николи # 103 на замену старому длинному имени.

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

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

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

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

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

Смотрите также

Рекомендации

  1. ^ а б Кнут, Дональд (2011), «Сувениры головоломки Николи», Избранные статьи о развлечениях и играх, CSLI Publications, стр. 473–476..
  2. ^ Эрих Фридман. «Жемчужные головоломки NP-Complete». В подготовке. 2002 г. [1].

внешняя ссылка