2
$\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:

  • 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.

$\endgroup$
4
  • $\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, 2016 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, 2016 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, 2016 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, 2016 at 9:27

2 Answers 2

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'
$\endgroup$
8
  • $\begingroup$ Thanks for your answer! I will check your solution out! Very nice answer! :) Thanks again! $\endgroup$
    – user30626
    Sep 30, 2016 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, 2016 at 9:43
  • $\begingroup$ Maybe you forgot to paste the rotate function? $\endgroup$
    – user30626
    Sep 30, 2016 at 14:58
  • $\begingroup$ @stackExhangeUser eh, I guess I did forget about it... $\endgroup$
    – ffao
    Sep 30, 2016 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, 2016 at 13:54
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ A meet-in-the-middle approach could help, although this puzzle may not explode quickly enough for it to matter. $\endgroup$ Mar 25 at 0:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.