# The Hamiltonian problem on Polyominoes

A polyomino is a connected subset of $\mathbb{Z}^2$ - a set of squares joined along their edges such that the resulting form is connected (or, more shortly, a generalized form of Tetris cube). A polyomino can be easily thought of as graph with vertices being elements of $\mathbb{Z}^2$ and edges between two vertices of hamming distance 1 (i.e. with one coordinate equal and the other different by 1).

The Hamiltonian path/cycle problem is the problem of determining for a given graph whether it contains a path/cycle that visits every vertex exactly once. It is known to be NP-complete for general graphs and even for planar graphs. My question is whether it's still NP-complete when restricting the graphs to be polyominoes (and if it is NP-complete, how it is shown).

-

This problem (both the path version and the circuit version) was shown to be NP-complete by Itai, Papadimitriou and Szwarcfiter [IPS82] by a reduction from a special case of the Hamiltonian circuit problem for planar graphs.

[IPS82] Alon Itai, Christos H. Papadimitriou and Jayme Luiz Szwarcfiter. Hamilton paths in grid graphs. SIAM Journal on Computing, 11(4):676–686, 1982. http://dx.doi.org/10.1137/0211056

-