Сумка (пазл)
Сумка играется на прямоугольной сетке, обычно состоящей из пунктирных линий, в которых в некоторых ячейках появляются числа.
Цель состоит в том, чтобы нарисовать одну непрерывную петлю вдоль линий сетки, которая содержит все числа в сетке. Кроме того, каждое число обозначает сумму всех ячеек, видимых в любом ортогональном направлении до достижения линии цикла. Например, к ячейке 2 будет примыкать одна ячейка, за которой следует стенка петли. Другими словами, если мы рассматриваем петлю как стену, каждое число обозначает количество ячеек, которые можно увидеть из ячейки с номером, если смотреть ортогонально, включая саму ячейку.
Самая простая отправная точка - найти «максимальную ячейку»; то есть пронумерованная ячейка, которая, если стены не находятся на максимально возможном расстоянии, номер не выполняется. Например, в сетке 10x10, которую еще не начали решать, 19-ячейка является максимальной ячейкой, поскольку, если бы четыре стены не находились на краях сетки, количество видимых ячеек было бы недостаточным. После некоторого прогресса появляются «минимальные ячейки», где, если стены не находятся на минимально возможном расстоянии, число не выполняется.
Многие методы решения для Bag очень похожи на те, что используются для Kuromasu , так как правила также очень похожи. Наиболее заметным отличием является использование цикла как части решения, а не заштрихованных ячеек.
Этот вопрос решения является NP-полным . Это доказывается сведением задачи принятия решения о раскрашиваемости планарного графа в 3 цвета , который, как известно, является NP-полным, к задаче о загоне.
