An unsolved Bag puzzle
The same puzzle, solved

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

  1. ↑ Friedman, Erich. "Corral Puzzles are NP-complete". Archived from the original on 13 June 2012. Retrieved 10 July 2016.


This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.