Title :
Satogaeri, Hebi, and Suraromu Are NP-Complete
Author :
Shohei Kanehiro;Yasuhiko Takenaga
Author_Institution :
Grad. Sch. of Inf. &
fDate :
7/1/2015 12:00:00 AM
Abstract :
Pencil puzzles are the puzzles such that people write answers on problems printed on paper. In this paper, we deal with three pencil puzzles, Satogaeri, Hebi and Suraromu. We show that the problems to decide the solvability of these puzzles are NP-complete. Also, in all of these puzzles, we show that there exist the rules without which the puzzles remain NP-complete.
Keywords :
"Logic gates","Wires","Games","Polynomials","Tracking","Turning","Scientific computing"
Conference_Titel :
Applied Computing and Information Technology/2nd International Conference on Computational Science and Intelligence (ACIT-CSI), 2015 3rd International Conference on
DOI :
10.1109/ACIT-CSI.2015.17
