Bag (puzzle) on:
[Wikipedia]
[Google]
[Amazon]
Bag (also called ''Corral'' or ''Cave'') is a binary-determination
Nikoli's Japanese page on ''Bag''
- describes some helpful solution strategies.
Logic puzzles Japanese games {{game-stub
Bag (also called ''Corral'' or ''Cave'') is a binary-determination logic puzzle
A logic puzzle is a puzzle deriving from the mathematical field of deduction.
History
The logic puzzle was first produced by Charles Lutwidge Dodgson, who is better known under his pen name Lewis Carroll, the author of ''Alice's Adventures in W ...
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 forKuromasu
, abbreviated or , is a binary-determination logic puzzle published by Nikoli (publisher), Nikoli. , one book consisting entirely of puzzles has been published by Nikoli.
Rules
is played on a rectangular grid. Some of these cells have number ...
, 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? This decision question isNP-complete
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying ...
. 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
*List of Nikoli puzzle types is a Japanese publisher that specializes in games and, especially, logic puzzles. ''Nikoli'' is also the nickname of a quarterly magazine (whose full name is ''Puzzle Communication Nikoli'') issued by the company in Tokyo. ''Nikoli'' was establish ...
* :Logic puzzles
References
External links
Nikoli's Japanese page on ''Bag''
- describes some helpful solution strategies.
Logic puzzles Japanese games {{game-stub