Score: 0
Wataridori is NP-Complete
Published: January 14, 2026 |
arXiv ID: 2601.09345v1
By: Suthee Ruangwises
Wataridori is a pencil puzzle involving drawing paths to connect all circles in a rectangular grid into pairs, in order to satisfy several constraints. In this paper, we prove that deciding solvability of a given Wataridori puzzle is NP-complete via reduction from Numberlink, another pencil puzzle that has already been proved to be NP-complete.
Similar Papers
85%
NP-Completeness Proofs of All or Nothing and Water Walk Using the T-Metacell Framework
Computational Complexity
Solves tricky puzzles by finding a hidden path.
24 Oct 2025
0
85%
Computational Complexity and Integer Programming Formulation of the Oredango Puzzle
Computational Complexity
Makes hard puzzles solvable by computers.
13 Mar 2025
0
84%
Evolomino is NP-complete
Computational Complexity
Makes a hard puzzle game even harder to solve.
5 Feb 2025
0