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?
Are Flow Free puzzles NP-hard?
np hard;square grid
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): 17I did not check the fine print.Added. Following a comment from domotorp, Numberlink usually has an additional constraint. Indeed, quoting from Adcock etal:Our hardness result can be compared to two previous NP-hardness proofs: Lynch's 1975 proof without the cover all vertices constraint, and Kotsuma and Takenaga's 2010 proof when the paths are restricted to have the fewest possible corners within their homotopy class. Adcock et al. Zig-Zag Numberlink is NP-Complete, Journal of Information Processing 23 (2015) 239-245, doi:10.2197/ipsjjip.23.239