Computational Complexity of Nurimisaki and Sashigane
Chuzo IWAMOTO, Tatsuya IDE · IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences · 2020
Nurimisaki and Sashigane are Nikoli's pencil puzzles. We study the computational complexity of Nurimisaki and Sashigane puzzles. It is shown that deciding whether a given instance of each puzzle has a solution is NP-complete.