1
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ How about a brute-force method. attempting all possibilities up to 12 moves would be less than a million attempts, which is easily reachable with a computer. $\endgroup$ – Tony Ruth Sep 30 '16 at 5:33
  • $\begingroup$ The problem is, that for example puzzles with 9 animals can have solutions with up to 40 moves, so brute force might be an option for smaller puzzles. $\endgroup$ – user30626 Sep 30 '16 at 5:36
  • $\begingroup$ About the UI: if I solve a puzzle and click on the "back" button, I should go to the previous puzzle, not the next. There should be an easier way to select puzzles too, clicking the forward arrow 219 times was not very nice :( $\endgroup$ – ffao Sep 30 '16 at 5:43
  • $\begingroup$ Also about the UI - I deliberately didn't read your explanation of how to play, and tried to figure it out. Fine when you're doing 4, not obvious when you're doing 5, HARD to figure out what's going on when you're doing 6. I'd recommend animating the swaps to make it more obvious what's happening $\endgroup$ – Joe Sep 30 '16 at 9:27
  • $\begingroup$ Thanks for your comments. I am working on making more easy to navigate through the puzzles. I will think about animation! thanks for your input! $\endgroup$ – user30626 Sep 30 '16 at 9:39
2
$\begingroup$

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'
Improve this answer
$\endgroup$
8
  • $\begingroup$ Thanks for your answer! I will check your solution out! Very nice answer! :) Thanks again! $\endgroup$ – user30626 Sep 30 '16 at 9:40
  • $\begingroup$ I have a question to your answer: you write rotate(p[1:-1]) and rotate(rot[1:-1]) but you give no function rotate or did I miss something? $\endgroup$ – user30626 Sep 30 '16 at 9:43
  • $\begingroup$ Maybe you forgot to paste the rotate function? $\endgroup$ – user30626 Sep 30 '16 at 14:58
  • $\begingroup$ @stackExhangeUser eh, I guess I did forget about it... $\endgroup$ – ffao Sep 30 '16 at 15:55
  • 1
    $\begingroup$ @stackExchangeUser Are you sure you inputted puzzle 324 right? "print solve([4,7,6,5,1,3,2])" gives me the valid solution XAXABXXBXXXX (PS: note that this is a proof of concept to show how the algorithm works, I expect you to be able to build your own program that implements the algorithm without bugs if I did make any :P) $\endgroup$ – ffao Oct 1 '16 at 13:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy