ASP-Completeness of Hamiltonicity in Grid Graphs, with Applications to Loop Puzzles

MIT Hardness Group, Josh Brunner, Lily Chung +4

We prove that Hamiltonicity in maximum-degree-3 grid graphs (directed or undirected) is ASP-complete, i.e., it has a parsimonious reduction from every NP search problem (including…