Сумка (головоломка)

Bag (также называемый Corral или Cave с двоичным определением, ) — логическая головоломка опубликованная Nikoli .

Правила

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

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

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

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

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

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

Вопрос для принятия решения (Фридман, 2002): Есть ли решение для данного примера Corral Puzzle? ^[1]

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

См. также

Ссылки

^ Фридман, Эрих. «Загадки корралов являются NP-полными» . Архивировано из оригинала 13 июня 2012 года . Проверено 10 июля 2016 г.

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

Японская страница Николи о сумке ^{[ постоянная мертвая ссылка ]}
«Лучше знать загон» — описывает некоторые полезные стратегии решения.
Информационная страница о Коррале, в основном на немецком языке.

Эта игрой статья, связанная с , незавершена . Вы можете помочь Википедии, расширив ее .

[1] Фридман, Эрих. «Загадки корралов являются NP-полными» . Архивировано из оригинала 13 июня 2012 года . Проверено 10 июля 2016 г.

[1]