Slant/Gokigen Naname is NP-complete, and Some Variations are in P
arXiv:2502.13536
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.
9 pages, 12 figures. Appeared at the Canadian Conference on Computational Geometry 2024 (CCCG 2024)