[UL97] show that Hamiltonicity of a solid grid graph
can be decided in polynomial time.
Thus we can decide whether there is a tour of length equal to the
number of vertices.
In contrast, deciding Hamiltonicity is NP-hard in general planar grid graphs
[ABD+01] observe that finding the shortest tour
is polynomially solvable when restricted to thin grid graphs,
i.e., grid graphs that do not contain an induced
This problem asks about replacing the thin restriction with the