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:

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

• I could possibly implement automatic hints in the game.

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'

Answer 2

The usual approach to finding a shortest plan is by doing a breadth first search from the starting state, until the goal state is reached, as follows.

1. Initialize a (first in first out) queue $Q$, and a hashset $V$ (to store which states have already been visited);
2. Enqueue the starting position $s_0$ in $Q$;
3. Add the starting position to a hashset of already visited states;
4. While $Q$ is not empty
   • dequeue a state $s$;
   • construct $s$'s three descendants $s_A$, $s_X$, $s_B$ that result from applying each of the three operations, and store who their parent is and which operation created them (to be able to reconstruct the sequence of operations later);
   • check for each descendant whether it is the goal, and if so, return it;
   • if it is not the goal, check if it's in $V$. If it isn't, add it to $V$ and enqueue it in $Q$.

This guarantees that a solution with the minimum number of operations will be found. It may not be unique. The order in which the descendants are constructed determines which shortest plan is found first.