Bolsa (rompecabezas)
La bolsa se juega en una cuadrícula rectangular, generalmente de líneas discontinuas, en la que aparecen números en algunas de las celdas.
El objetivo es dibujar un bucle único y continuo a lo largo de las líneas de la cuadrícula, que contiene todos los números de la cuadrícula. Además, cada número indica la suma de todas las celdas visibles en cualquier dirección ortogonal antes de alcanzar la línea del bucle. Por ejemplo, una celda 2 tendrá una celda adyacente, seguida de una pared del bucle. En otras palabras, si tratamos el bucle como una pared, cada número denota el número de celdas que se pueden ver desde la celda con el número cuando se mira ortogonalmente, incluida la celda misma.
El punto de partida más fácil es encontrar una "celda máxima"; es decir, una celda numerada que si las paredes no están a la máxima distancia posible, el número no se satisface. Por ejemplo, en una cuadrícula de 10x10 que no se ha empezado a resolver, una celda de 19 es una celda máxima, ya que si las cuatro paredes no están en los bordes de la cuadrícula, el número de celdas visibles no sería suficiente. Después de hacer algunos progresos, aparecen "celdas mínimas", donde si las paredes no están a la distancia mínima posible, el número no se satisface.
Muchos de los métodos de solución para Bag son muy similares a los utilizados para Kuromasu , ya que las reglas también son muy similares. La diferencia más notable es el uso del bucle como parte de la solución, a diferencia de las celdas sombreadas.
Esta pregunta de decisión es NP-completa . Esto se demuestra al reducir el problema de decisión de decidir la 3-colorabilidad de un gráfico plano , que se sabe que es NP-completo, a un Rompecabezas de Corral.
