NP-Completeness Proofs of All or Nothing and Water Walk Using the T-Metacell Framework
Published: Oct 24, 2025
Last Updated: Oct 24, 2025
Authors:Pakapim Eua-anant, Papangkorn Apinyanon, Thunyatorn Jirachaisri, Nantapong Ruangsuksriwong, Suthee Ruangwises
Abstract
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.