The Hamiltonian cycle problem is an important problem in graph theory and
computer science. It is a special case of the famous traveling salesman problem.
A signi cant amount of research has been done on the special cases of
nding Hamiltonian cycles in subgraphs of triangular, square and hexagonal
grids. However, there is little work on more complicated grids. In this paper,
we investigate the hardness of Hamiltonian cycle problem in grid graphs of
semiregular tessellations, which are tessellations formed by two or more kinds of
regular polygons. There are only eight semiregular tessellations, and we prove
that the Hamiltonian cycle problem in all of them are NP-complete by reducing
from NP-complete problems, such as the Hamiltonian cycle problem in max
degree 3 bipartite planar graphs. Knowing the NP-completeness of Hamiltonian
cycle problem in semiregular grids indicates that there will not be any
polynomial time algorithm that solves the Hamiltonian path problem in these
tessellations if NP does not equal to P, which helps show the limits of ecient
motion planning algorithms and provides new information about what makes
problems computationally dicult to solve.