NP-Completeness Proofs of All or Nothing and Water Walk Using the T-Metacell Framework

2025/10/24 by Eua-anant, Pakapim, Apinyanon, Papangkorn, Jirachaisri, Thunyatorn +2
#68Q17 #Computational Complexity (cs.CC) #F.2.2 #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2510.21938

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.

Citations

• A Framework for Loop and Path Puzzle Satisfiability NP-Hardness Results
• Tatamibari is NP-complete
• Zig-Zag Numberlink is NP-Complete

Related

• Ice Walk is ASP-Complete
• ASP-Completeness of Hamiltonicity in Grid Graphs, with Applications to Loop Puzzles
• A Framework for Loop and Path Puzzle Satisfiability NP-Hardness Results
• ASP-Completeness Proofs of Puzzles Using the T-Metacell Framework
• A new approach for a proof that P is NP