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:
- 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
- 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
- Rotate $rot$
- 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'