Slant/Gokigen Naname is NP-complete, and Some Variations are in P

Jayson Lynch, Jack Spalding-Jamieson

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 constraint…