Example 1 - Fifteen Puzzle

There used to be a puzzle, sometimes called the 15 puzzle, consisting of 15 sliding plastic tiles in a 4 by 4 frame. There is only one space without a tile, so the only moves possible are to slide the adjacent tiles into that space.

The tiles have letters or numbers on them and the goal is to get them in a certain order.

So for the first move, in this starting position, there are only 2 moves possible:

• move tile 1 into the space
• move tile 4 into the space

Say we move tile 1:

Now there are 3 moves possible:

• move tile 1 into the space (inverse of first move)
• move tile 2 into the space
• move tile 5 into the space

• We could think of the position of all the tiles as being its state. There is then a mapping from state to state, but this mapping is partial because only certain moves will be possible depending on where the space is.

• Rather than one set of endo functions we could have a set of states, one for each possible location of the space. So now instead of the functions being endofunctions they go between these states. These functions are no longer partial but they are still permutations.