Computational Complexity of Usowan Puzzles

Chuzo IWAMOTO  Masato HARUISHI  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E101-A   No.9   pp.1537-1540
Publication Date: 2018/09/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E101.A.1537
Type of Manuscript: Special Section LETTER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
Usowan,  pencil puzzle,  NP-complete,  

Full Text: PDF(428KB)
>>Buy this Article


Summary: 
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.