Bag (also called Corral or Cave) is a binary-determination logic puzzle published by Nikoli.
Rules
Bag is played on a rectangular grid, usually of dashed lines, in which numbers appear in some of the cells.
The object is to draw a single, continuous loop along the lines of the grid that contains all the numbers on the grid. Each number indicates the total number of cells visible in any orthogonal direction before a line of the loop is reached, plus the cell itself. For example, a 2-cell will have one cell adjacent to it, followed by a wall of the loop.
Solution methods
The easiest starting place is to find a "maximum cell"; that is, a numbered cell which if the walls are not at the maximum distance possible, the number is not satisfied. For example, in a 10x10 grid which has not started to be solved, a 19-cell is a maximum cell, since if the four walls are not at the edges of the grid, the number of cells visible wouldn't be enough. After making some progress, "minimum cells" appear, where if the walls are not at the minimum distance possible, the number is not satisfied.
Many of the solution methods for Bag are very similar to those used for Kuromasu, as the rules are also very similar. The most notable difference is the use of the loop as a part of the solution, as opposed to shaded cells.
Computational complexity
Decision question (Friedman, 2002): Does a given instance of Corral Puzzle have a solution?[1]
This decision question is NP-complete. 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.
See also
References
- ^ Friedman, Erich. "Corral Puzzles are NP-complete". Archived from the original on 13 June 2012. Retrieved 10 July 2016.
External links
- Nikoli's Japanese page on Bag[permanent dead link]
- Better Know a Corral - describes some helpful solution strategies.
- Informative page on Corral, mostly in German.
 | This game-related article is a stub. You can help Wikipedia by expanding it. |
This page was last edited on 23 April 2022, at 18:44