ASP-Completeness Proofs of Puzzles Using the T-Metacell Framework
By: Nattapol Kiatchaipipat, Suthee Ruangwises
Potential Business Impact:
Solves hard pencil puzzles using a new logic trick.
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.
Similar Papers
NP-Completeness Proofs of All or Nothing and Water Walk Using the T-Metacell Framework
Computational Complexity
Solves tricky puzzles by finding a hidden path.
Man, these New York Times games are hard! A computational perspective
Computational Complexity
Makes New York Times games harder to solve.
A Solver-in-the-Loop Framework for Improving LLMs on Answer Set Programming for Logic Puzzle Solving
Artificial Intelligence
Helps computers solve puzzles by learning from mistakes.