ASP-Completeness Proofs of Puzzles Using the T-Metacell Framework

2025/08/15 by Kiatchaipipat, Nattapol, Ruangwises, Suthee
#Computational Complexity (cs.CC) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2508.11570

Abstract

Pencil puzzles are puzzles that can be solved by writing down solutions on a paper, using only logical reasoning. In this paper, we utilize the "T-metacell" framework developed by Tang and the MIT Hardness Group to prove the ASP-completeness of four new pencil puzzles: Grand Tour, Entry Exit, Yagit, and Zahlenschlange. The results demonstrate how versatile the framework is, offering new insights into the computational complexity of problems with various constraints.

Citations

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

Related

• NP-Completeness Proofs of All or Nothing and Water Walk Using the T-Metacell Framework
• A Framework for Loop and Path Puzzle Satisfiability NP-Hardness Results
• Using Small MUSes to Explain How to Solve Pen and Paper Puzzles
• Ice Walk is ASP-Complete
• Computational Complexity and Integer Programming Formulation of the Oredango Puzzle