Bag (puzzle)

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, which contains all the numbers on the grid. Additionally, each number denotes the sum of all cells visible in any orthogonal direction before line of the loop is reached. For example, a 2 cell will have one cell adjacent to it, followed by a wall of the loop. In other words, if we treat the loop as a wall, each number denotes the number of cells can be seen from the cell with the number when looking orthogonally, the cell itself included.

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". 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.