Computational Complexity of Usowan Puzzles
Chuzo IWAMOTO, Masato Haruishi · IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences · 2018
Usowan is one of Nikoli's pencil puzzles. We study the computational complexity of Usowan puzzles. It is shown that deciding whether a given instance of the Usowan puzzle has a solution is NP-complete.