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