Satogaeri, Hebi, and Suraromu Are NP-Complete
Shohei Kanehiro, Yasuhiko Takenaga · 2015
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.