NP-Completeness Proofs of All or Nothing and Water Walk Using the T-Metacell Framework
By: Pakapim Eua-anant , Papangkorn Apinyanon , Thunyatorn Jirachaisri and more
Potential Business Impact:
Solves tricky puzzles by finding a hidden path.
All or Nothing and Water Walk are pencil puzzles that involve constructing a continuous loop on a rectangular grid under specific constraints. In this paper, we analyze their computational complexity using the T-metacell framework developed by Tang and MIT Hardness Group. We establish that both puzzles are NP-complete by providing reductions from the problem of finding a Hamiltonian cycle in a maximum-degree-3 spanning subgraph of a rectangular grid graph.
Similar Papers
ASP-Completeness Proofs of Puzzles Using the T-Metacell Framework
Computational Complexity
Solves hard pencil puzzles using a new logic trick.
Lower bounds on pure dynamic programming for connectivity problems on graphs of bounded path-width
Computational Complexity
Proves some computer problems are very hard.
Man, these New York Times games are hard! A computational perspective
Computational Complexity
Makes New York Times games harder to solve.