Slant/Gokigen Naname is NP-complete, and Some Variations are in P
classification
💻 cs.DM
cs.CGcs.DS
keywords
constraintsnp-completepuzzleslantsomealgorithmsconnectivitycorrespond
read the original abstract
In this paper we show that a generalized version of the Nikoli puzzle Slant is NP-complete. We also give polynomial time algorithms for versions of the puzzle where some constraints are omitted. These problems correspond to simultaneously satisfying connectivity and vertex degree constraints in a grid graph and its dual.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.