Sliding puzzles and rotating puzzles on graphs

Sliding puzzles on graphs are generalizations of the Fifteen Puzzle. Wilson has shown that the sliding puzzle on a 2-connected graph always generates all even permutations of the tiles on the vertices of the graph, unless the graph is isomorphic to a cycle or the graph θ 0 [R.M. Wilson, Graph puzzles, homotopy, and the alternating group, J. Combin. Theory Ser. B 16 (1974) 86–96]. In a rotating puzzle on a graph, tiles are allowed to be rotated on some of the cycles of the graph. It was shown by Scherphuis that all even permutations of the tiles are also obtainable for the rotating puzzle on a 2-edge-connected graph, except for a few cases. In this paper, Scherphuis’ Theorem is generalized to every connected graph, and Wilson’s Theorem is derived from the generalized Scherphuis’ Theorem, which will give a uniform treatise for these two families of puzzles and reveal the structural relation of the graphs of the two puzzles.