  We study a new reconfiguration problem inspired by classic mechanical
puzzles: a colored token is placed on each vertex of a given graph; we are also
given a set of distinguished cycles on the graph. We are tasked with
rearranging the tokens from a given initial configuration to a final one by
using cyclic shift operations along the distinguished cycles. We first
investigate a large class of graphs, which generalizes several classic puzzles,
and we give a characterization of which final configurations can be reached
from a given initial configuration. Our proofs are constructive, and yield
efficient methods for shifting tokens to reach the desired configurations. On
the other hand, when the goal is to find a shortest sequence of shifting
operations, we show that the problem is NP-hard, even for puzzles with tokens
of only two different colors.
