Bag (puzzle)

Bag (also called Corral or Cave) is a binary-determination logic puzzle published by Nikoli.

Bag is played on a rectangular grid, usually of dashed lines, in which numbers appear in some of the cells.

The most notable difference is the use of the loop as a part of the solution, as opposed to shaded cells.

Decision question (Friedman, 2002): Does a given instance of Corral Puzzle have a solution?

This is proven by reducing the decision problem of deciding the 3-colorability of a planar graph, which is known to be NP-complete, to a Corral Puzzle.