arXiv:1410.5845cs.CC
Zig-Zag Numberlink is NP-Complete
Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.
Abstract
When can $t$ terminal pairs in an $m \times n$ grid be connected by $t$ vertex-disjoint paths that cover all vertices of the grid? We prove that this problem is NP-complete. 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. The latter restriction is a common form of the famous Nikoli puzzle \emph{Numberlink}; our problem is another common form of Numberlink, sometimes called \emph{Zig-Zag Numberlink} and popularized by the smartphone app \emph{Flow Free}.
At the time I posted this submission, the proof was `sorry` and `axiom` free but had 154 `native_decide`s. The proof is enumeration heavy and so for efficiencies sake, the `native_decide`s were used to speed up proof compilation. Since the submission here, I've had Claude remove…
zzyzekView on HNParent context