  We propose a new kind of sliding-block puzzle, called Gourds, where the
objective is to rearrange 1 x 2 pieces on a hexagonal grid board of 2n + 1
cells with n pieces, using sliding, turning and pivoting moves. This puzzle has
a single empty cell on a board and forms a natural extension of the 15-puzzle
to include rotational moves. We analyze the puzzle and completely characterize
the cases when the puzzle can always be solved. We also study the complexity of
determining whether a given set of colored pieces can be placed on a colored
hexagonal grid board with matching colors. We show this problem is NP-complete
for arbitrarily many colors, but solvable in randomized polynomial time if the
number of colors is a fixed constant.
