Computational Complexity of Usowan Puzzles
Authors:
- 1 September 2018
- journal article
- research article
- Published by Institute of Electronics, Information and Communications Engineers (IEICE) in IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
- Vol. E101.A (9) , 1537-1540
Abstract
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.Keywords
This publication has 7 references indexed in Scilit:
- The Complexity of Generalized Pipe Link PuzzlesJournal of Information Processing, 2017
- Zig-Zag Numberlink is NP-CompleteJournal of Information Processing, 2015
- Fillmat is NP-Complete and ASP-CompleteJournal of Information Processing, 2015
- Yosenabe is NP-completeJournal of Information Processing, 2014
- Kurodoko is NP-CompleteJournal of Information Processing, 2012
- Hashiwokakero is NP-completeInformation Processing Letters, 2009
- Games, Puzzles, and Computation2009