Сумка (пазл) - Bag (puzzle)

Мешок (также называемый Загон или же Пещера) является двоичным определением логическая головоломка опубликовано Николи.

Правила

Мешок играется на прямоугольной сетке, обычно из пунктирных линий, в некоторых ячейках которой указаны числа.

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

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

Самая простая отправная точка - найти «максимальную ячейку»; то есть пронумерованная ячейка, которая, если стены не находятся на максимально возможном расстоянии, номер не удовлетворяется. Например, в сетке 10x10, решение которой еще не началось, 19 ячеек - это максимальная ячейка, поскольку, если четыре стены не находятся на краях сетки, количества видимых ячеек будет недостаточно. После некоторого прогресса появляются «минимальные ячейки», где, если стены не находятся на минимально возможном расстоянии, количество не удовлетворяется.

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

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

Решающий вопрос (Friedman, 2002): есть ли решение для данного экземпляра Corral Puzzle?[1]

Этот вопрос решения является NP-полным. Это доказано уменьшением проблемы решения решение 3-раскрашиваемости плоского графа, которая, как известно, является NP-полной, загадки загона.

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

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

  1. ^ Фридман, Эрих. «Загадки загона NP-полные». Получено 10 июля 2016.

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