Polynomial-Time Reductions from 3SAT to Kurotto and Juosan Puzzles

Chuzo IWAMOTO  Tatsuaki IBUSUKI  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E103-D   No.3   pp.500-505
Publication Date: 2020/03/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2019FCP0004
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science — Frontiers of Theory of Computation and Algorithm —)
Category: 
Keyword: 
Kurotto,  Juosan,  pencil puzzle,  NP-complete,  

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




Summary: 
Kurotto and Juosan are Nikoli's pencil puzzles. We study the computational complexity of Kurotto and Juosan puzzles. It is shown that deciding whether a given instance of each puzzle has a solution is NP-complete.