Permutation puzzles

A one person game is a sequence of moves following certain rules satisfying

  • there are finitely many moves at each stage,
  • there is a finite sequence of moves which yields a solution,
  • there are no chance or random moves,
  • there is complete information about each move,
  • each move depends only on the present position, not on the existence or non-existence of a certain previous move (such as chess, where castling is made illegal if the king has been moved previously).

A permutation puzzle is a one person game (solitaire) with the following five properties listed below. Before listing the properties, we define the puzzle position to be the set of all possible legal moves. The five properties of a permutation puzzle are:

  1. for some n > 1 depending only on the puzzle’s construction, each move of the puzzle corresponds to a unique permutation of the numbers in T = {1, 2, …, n},
  2. if the permutation of T in (1) corresponds to more than one puzzle move then the the two positions reached by those two respective moves must be indistinguishable,
  3. each move, say M, must be “invertible” in the sense that there must exist another move, say M-1, which restores the puzzle to the position it was at before M was performed,
  4. if M1 is a move corresponding to a permutation fof T and if M2 is a move corresponding to a permutation fof T then M1*M2 (the move M1 followed by the move M2) is either
    • not a legal move, or
    • corresponds to the permutation f1*f2.