A Framework for Loop and Path Puzzle Satisfiability NP-Hardness Results

2022/02/04 by Tang, Hadyn · 2 citations
#Computational Complexity (cs.CC) #F.1.3 #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2202.02046

Abstract

Building on the results published in arxiv:2004.12849 we present a general framework for demonstrating the NP-hardness of satisfying many genres of loop and path puzzles using a 'T-metacell' gadget. We then use this to prove the NP-completeness of a variety of such genres, and discuss some of the limitations of this gadget.

Cited by

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

Related

• On the NP-Completeness of Satisfying Certain Path and Loop Puzzles
• NP-Completeness Proofs of All or Nothing and Water Walk Using the T-Metacell Framework
• ASP-Completeness Proofs of Puzzles Using the T-Metacell Framework
• Mastermind is NP-Complete
• NP-Hardness of a 2D, a 2.5D, and a 3D Puzzle Game