Nagenawa is NP-Complete

Pencil-and-paper puzzles have been capturing the interest of the scientific community in recent years, especially the ones invented and popularized by the Japanese publisher Nikoli. The reason for this interest lies in the inherent difficulty of solving these puzzles, which has led to many studies on their computational complexity. Various Nikoli puzzles have been shown to be NP-complete, and a consistent decreasing trend has been observed before for the amount of time between the publication of a new Nikoli puzzle and the establishment of the puzzle's first hardness result (from gaps of almost 20 years for most of the company's older puzzles to gaps of less than 5 years for most of the newer ones). In this paper, we prove that Nagenawa, a Nikoli puzzle, is NP-complete.