def PossibleLegalMoves(current):
    """
    Returns a list of possible legal moves from the current state.

    Moves consist of moving right 1 unit, moving right 2 units, move left 1 unit, move left 2 units.
    Moves are encoded as tuple where the first element is the old position of the vacant rock and the second 
    position is the new position of the vacant rock.

    """
    GreenFrogs = set(["A","B","C"])
    BrownFrogs = set(["X","Y","Z"])
    GreenIndex = {"A":0, "B":1,"C":2}
    BrownIndex = {"X":4, "Y":5,"Z":6}
    moves_index= [-2,-1,1,2]
    moves = list()
    vacantRock = current.index("_")
    for i in moves_index:
        if 0<=(i+vacantRock)<= 6:
            if (current[i+vacantRock] in GreenFrogs) and (vacantRock > GreenIndex[current[i+vacantRock]]):
                moves.append((vacantRock,i+vacantRock))
            elif (current[i+vacantRock] in BrownFrogs) and (vacantRock < BrownIndex[current[i+vacantRock]]):
                moves.append((vacantRock,i+vacantRock))
    return moves