A "Flow Free" puzzle consists of a positive integer $n$ and a set of (unordered) pairs of distinct vertices in the $n \times n$ grid graph such that each vertex is in at most one pair. A solution to such a puzzle is a set of undirected paths in the graph such that each vertex is in exactly one path and each path's set of ends is one of the puzzle's pairs of vertices. This image is an example of a Flow Free puzzle, and this image is an example of a solution to a different Flow Free puzzle.
Is the problem "Does there exist a solution to this Flow Free puzzle?" NP-hard? Does it matter whether $n$ is given in unary or binary?
Asked By : Ricky Demer
Answered By : Hendrik Jan
In the terminology of Nikoli Puzzles this is known as "Nanbarinku" or "Numberlink". The description does not always explicitly mention all squares must be covered, but this is indeed the case in all solutions I checked.
According to Wikipedia Numberlink the problem is NP complete, with reference: Kotsuma, Kouichi; Takenaga, Yasuhiko (March 2010), NP-Completeness and Enumeration of Number Link Puzzle, IEICE technical report. Theoretical foundations of Computing 109 (465): 1–7
I did not check the fine print.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/31938
0 comments:
Post a Comment
Let us know your responses and feedback