For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Polynomial-Time Reductions from 3SAT to Kurotto and Juosan Puzzles
Chuzo IWAMOTO Tatsuaki IBUSUKI
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2020/03/01
Online ISSN: 1745-1361
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science — Frontiers of Theory of Computation and Algorithm —)
Kurotto, Juosan, pencil puzzle, NP-complete,
Full Text: PDF(770.5KB)>>
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.