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

February 19, 2025 · The Ethereal · 🏛 arXiv.org

🔮 THE ETHEREAL: The Ethereal
Pure theory — exists on a plane beyond code

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Jayson Lynch, Jack Spalding-Jamieson arXiv ID 2502.13536 Category cs.DM: Discrete Mathematics Cross-listed cs.CG, cs.DS Citations 0 Venue arXiv.org Last Checked 5 months ago
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.
Community shame:
Not yet rated
📄 View on arXiv 🌐 View on ar5iv 📑 PDF 🎉 Report Code Found
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

📜 Similar Papers

In the same crypt — Discrete Mathematics