Algorithm for solving the permutation puzzle Tricky Animals

Question

I have developed a game called Tricky Animals where the goal is to reorder the animals in the right order with three permutations: $A = (1,2), X = (2,3,..,n-1), B = (n-1, n)$. The game can be played for free on http://www.tricky-animals.de. Notice that $A,X,B$ generate the whole symmetric group, hence every puzzle can be solved.

Now my question is this:

Is there an algorithm on how to solve a given puzzle (with possibly a minimal number of steps)? If so, that would be great, since it means:

a) I can calculate how difficult the puzzle is, based on the number of steps to solve it

b) I could possibly implement automatic hints in the game.

Thanks for your time!

P.S: If you enjoy playing permutation puzzles, try solving puzzle 220 with 6 steps! ;)

Edit: I updated the site http://www.tricky-animals.de to better navigate through the puzzles, since most users don't want to click that often to navigate through the puzzles. (Thanks for your input on this!)

Now if you click on the animals at the top, the game will jump to the corresponding puzzle with the number of animals.

Answer 1

To get things started, here's a (greedy) algorithm that should solve most puzzles fairly quickly ($n$ is the length of the permutation):

• Let $rot$ be a rotation of $[2,n-1]$
• Repeat the following steps until $a$ is the identity permutation or only the extremes are switched:
  1. If $a[1]$ is equal to $rot[1]$, or $a[1]$ is 1 or $n$ and $a[2]$ is different from $rot[1]$, do move A
  2. If $a[n]$ is equal to $rot[n-2]$, or $a[n]$ is 1 or $n$ and $a[n-1]$ is different from $rot[n-2]$, do move B
  3. Rotate $rot$
  4. Do move X
• If the extremes are switched, unswitch them (by doing BXAXXXX...B).

In order to get a better solution, you might want to try all possible initial rotations (there are n-2 of them). This is an implementation in Python 2:

def rotate(l):
    return l[-1:] + l[:-1]

def get_moves(init, selected_rotation):
    target = range(1, len(init)+1)
    moves = ''

    p = init[:]
    rot = selected_rotation[:]

    while True:
        if (p[0] in [rot[0],rot[-1]] and p[1] != rot[1]) or (p[0] == rot[1]):
            p[0],p[1] = p[1],p[0]
            moves += 'A'

        if (p[-1] in [rot[0],rot[-1]] and p[-2] != rot[-2]) or (p[-1] == rot[-2]):
            p[-1],p[-2] = p[-2],p[-1]
            moves += 'B'

        if p == target:
            return moves
        if p[-1:] + p[1:-1] + p[:1] == target:
            return moves + 'BXA' + ('X'*(len(init)-3)) + 'B'

        p[1:-1] = rotate(p[1:-1])
        rot[1:-1] = rotate(rot[1:-1])
        moves += 'X'

        if p == target:
            return moves
        if p[-1:] + p[1:-1] + p[:1] == target:
            return moves + 'BXA' + ('X'*(len(init)-3)) + 'B'

def solve(init):
    n = len(init)
    bestmoves = ''
    rot = [1] + range(2, n) + [n]

    for rotation in xrange(n-2):
        m = get_moves(init, rot)
        if not bestmoves or len(m) < len(bestmoves):
            bestmoves = m
        rot[1:-1] = rotate(rot[1:-1])

    return bestmoves

Testing our implementation on Puzzle 220:

>>> print solve([4,3,6,2,5,1])
'ABXAXB'