[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
[IPS82].
[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
2×2 square.
This problem asks about replacing the thin restriction with the
solid restriction.