2025/02/19 by Jayson Lynch, Lynch, Jayson, Jack Spalding-Jamieson +1
Mathematics · #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Mathematics and Applications
paper · pdf · doi:10.48550/arxiv.2502.13536
openalex publication_date 2025/02/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.