Zig-Zag Numberlink is NP-Complete
Authors:
Open Access
- 1 January 2015
- journal article
- Published by Information Processing Society of Japan in Journal of Information Processing
- Vol. 23 (3) , 239-245
Abstract
When can t terminal pairs in an m × 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 Numberlink. Our problem is another common form of Numberlink, sometimes called Zig-Zag Numberlink and popularized by the smartphone app Flow Free.National Science Foundation (U.S.) (Grant CCF-1161626)United States. Defense Advanced Research Projects Agency (United States. Air Force Office of Scientific Research Grant FA9550-12-1-0423Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- Computational Complexity and an Integer Programming Model of ShakashakaIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2014
- Yosenabe is NP-completeJournal of Information Processing, 2014
- Kurodoko is NP-CompleteJournal of Information Processing, 2012
- Hashiwokakero is NP-completeInformation Processing Letters, 2009
- Games, Puzzles, and Computation2009
- A SURVEY OF NP-COMPLETE PUZZLESICGA Journal: The Journal of the Computer Games Community, 2008
- Number LinkThe Mathematica Journal, 2007
- Hamilton Paths in Grid GraphsSIAM Journal on Computing, 1982
- The equivalence of theorem proving and the interconnection problemACM SIGDA Newsletter, 1975