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.
Building similarity graph...
Analyzing shared references across papers
Loading...
Lucas T. Bordin
Andrei de A. S. Braga
Braulio Mello
Journal of Information Processing
Universidade Federal da Fronteira Sul
Building similarity graph...
Analyzing shared references across papers
Loading...
Bordin et al. (Thu,) studied this question.
www.synapsesocial.com/papers/69a7615fc6e9836116a2f3bf — DOI: https://doi.org/10.2197/ipsjjip.34.112