Let G and H be graphs with the same number of vertices. We introduce a graph puzzle (G, H) in which G is a board graph and the set of vertices of H is the set of pebbles. A configuration of H on G is defined as a bijection from the set of vertices of G to that of H. A move of pebbles is defined as exchanging two pebbles which are adjacent on both G and H. For a pair of configurations f and g, we say that g is equivalent to f if f can be transformed into g by a sequence of finite moves. If G is a 4 x 4 grid graph and H is a star, then the puzzle (G, H) corresponds to the well-known 15-puzzle. A puzzle (G, H) is called feasible if all the configurations of H on G are mutually equivalent. In this paper, we study the feasibility of the puzzle under various conditions. Among other results, for the case where one of the two graphs G and H is a cycle, a necessary and sufficient condition for the feasibility of the puzzle (G, H) is shown. (C) 2013 Elsevier B.V. All rights reserved.