[1,2,0,0], length = 4, n = 2

[0,0,2,1]

if tuple(successor) not in s:
    s.add(tuple(successor))

def solve_distinct_disks(length, n):



    board = [i + 1 if i < n else 0 for i in range(length)]
    solved = list(reversed(board))
    print board, solved
    if board == solved:
        return []
    d = collections.deque()
    s = set()
    d.append(([], board))
    while len(d) > 0:
        moves, current = d.popleft()
        for i, p in enumerate(current):
            if p != 0:
                if i + 1 < length and current[i + 1] == 0:
                    move = (i, i + 1)
                    successor = current[:]
                    successor[i] = 0
                    successor[i + 1] = p
                    if successor == solved:
                        return moves + [move]
                    if tuple(successor) not in s:
                        s.add(tuple(successor))
                        d.append((moves + [move], successor))
                elif i + 2 < length and current[i + 2] == 0:
                    move = (i, i + 2)
                    successor = current[:]
                    successor[i] = 0
                    successor[i + 2] = p
                    if successor == solved:
                        return moves + [move]
                    if tuple(successor) not in s:
                        s.add(tuple(successor))
                        d.append((moves + [move], successor))
                if i - 1 >= 0 and current[i - 1] == 0:
                    move = (i, i - 1)
                    successor = current[:]
                    successor[i] = 0
                    successor[i - 1] = p
                    if successor == solved:
                        return moves + [move]
                    if tuple(successor) not in s:
                        s.add(tuple(successor))
                        d.append((moves + [move], successor))
                elif i - 2 >= 0 and current[i - 2] == 0:
                    move = (i, i - 2)
                    successor = current[:]
                    successor[i] = 0
                    successor[i - 2] = p
                    if successor == solved:
                        return moves + [move]
                    if tuple(successor) not in s:
                        s.add(tuple(successor))
                        d.append((moves + [move], successor))

def solve_distinct_disks_2(length, n):



    board = [i + 1 if i < n else 0 for i in range(length)]
    solved = list(reversed(board))
    print board, solved

    if board == solved:
        return []

    d = collections.deque()
    s = set()
    d.append(([], board))

    while len(d) > 0:
        moves, current = d.popleft()
        s.add(tuple(current))

        for i, p in enumerate(current):
            if p != 0:
                if i + 1 < length and current[i + 1] == 0:
                    move = (i, i + 1)
                    successor = current[:]
                    successor[i] = 0
                    successor[i + 1] = p
                    if successor == solved:
                        return moves + [move]
                    if tuple(successor) not in s:
                        d.append((moves + [move], successor))
                elif i + 2 < length and current[i + 2] == 0:
                    move = (i, i + 2)
                    successor = current[:]
                    successor[i] = 0
                    successor[i + 2] = p
                    if successor == solved:
                        return moves + [move]
                    if tuple(successor) not in s:
                        d.append((moves + [move], successor))
                if i - 1 >= 0 and current[i - 1] == 0:
                    move = (i, i - 1)
                    successor = current[:]
                    successor[i] = 0
                    successor[i - 1] = p
                    if successor == solved:
                        return moves + [move]
                    if tuple(successor) not in s:
                        d.append((moves + [move], successor))
                elif i - 2 >= 0 and current[i - 2] == 0:
                    move = (i, i - 2)
                    successor = current[:]
                    successor[i] = 0
                    successor[i - 2] = p
                    if successor == solved:
                        return moves + [move]
                    if tuple(successor) not in s:
                        d.append((moves + [move], successor))

def solve_distinct_disks_3(length, n):



    board = [i + 1 if i < n else 0 for i in range(length)]
    solved = list(reversed(board))
    print board, solved

    if board == solved:
        return []

    d = collections.deque()
    s = set()
    d.append(([], board))

    while len(d) > 0:
        moves, current = d.popleft()

        if tuple(current) not in s:
            s.add(tuple(current))
            for i, p in enumerate(current):
                if p != 0:
                    if i + 1 < length and current[i + 1] == 0:
                        move = (i, i + 1)
                        successor = current[:]
                        successor[i] = 0
                        successor[i + 1] = p
                        if successor == solved:
                            return moves + [move]
                        d.append((moves + [move], successor))
                    elif i + 2 < length and current[i + 2] == 0:
                        move = (i, i + 2)
                        successor = current[:]
                        successor[i] = 0
                        successor[i + 2] = p
                        if successor == solved:
                            return moves + [move]
                        d.append((moves + [move], successor))
                    if i - 1 >= 0 and current[i - 1] == 0:
                        move = (i, i - 1)
                        successor = current[:]
                        successor[i] = 0
                        successor[i - 1] = p
                        if successor == solved:
                            return moves + [move]
                        d.append((moves + [move], successor))
                    elif i - 2 >= 0 and current[i - 2] == 0:
                        move = (i, i - 2)
                        successor = current[:]
                        successor[i] = 0
                        successor[i - 2] = p
                        if successor == solved:
                            return moves + [move]
                        d.append((moves + [move], successor))