有豹子,老虎,狮子,都一大一小,三个大的和小老虎都会划船,其他两个 不会划,每次只能过两个,大吃小（没有大的在保护就被吃掉）. 这2个动物怎样才能过河？ P.S. 算法还不完美，输出了多余的东东。

six_animals.py

#encoding=utf8
"""
有豹子,老虎,狮子,都一大一小,三个大的和小老虎都会划船,其他两个   
  不会划,每次只能过两个,大吃小（没有大的在保护就被吃掉）.   
  这2个动物怎样才能过河？
"""

from itertools import combinations

def is_bad(L):
    if 'a' in L and 'A' not in L:
        if 'B' in L or 'C' in L:
            return True
    if 'b' in L and 'B' not in L:
        if 'A' in L or 'C' in L:
            return True
    if 'c' in L and 'C' not in L:
        if 'A' in L or 'B' in L:
            return True
    return False

def get_ones(L):
    assert('o' in L)
    result = []
    for item in L:
        if item == 'o':
            continue
        if cannot_boat(item):
            continue
        TMP = L[:]
        TMP.remove(item)
        if is_bad(TMP):
            continue
        result.append(item)
    return result

def cannot_boat(a):
    return a in ('b', 'c')

def get_twos(L):
    assert('o' in L)
    LL = L[:]
    LL.remove('o')
    LL = [x for x in combinations(LL, 2)]
    result = []
    for x, y in LL:
        TMP = L[:]
        TMP.remove('o')
        TMP.remove(x)
        TMP.remove(y)
        if is_bad(TMP):
            continue
        if cannot_boat(x) and cannot_boat(y):
            continue
        result.append((x, y))
    return result

def get_key(Left, Right):
    L, R = Left[:], Right[:]
    L.sort()
    R.sort()
    key = "%s|%s" % (''.join(L), ''.join(R))
    return key

def start():
    Left, Right = ['A', 'B', 'C', 'a', 'b', 'c', 'o'], []
    solutions = []
    result = []
    D = {}
    flag = False
    while 1:
        if Left == []:
            # All animals on the other side
            break
        Current = Left if 'o' in Left else Right
        if not flag:
            for one in get_ones(Current):
                solutions.append((one, Left[:], Right[:]))
            for two in get_twos(Current):
                solutions.append((two, Left[:], Right[:]))
        boat, Left, Right = solutions.pop()
        flag = False

        key = get_key(Left, Right)
        D[key] = 1
        result.append((boat, Left[:], Right[:]))
        Left, Right, eaten = move_to_another_side(boat, Left, Right)
        key = get_key(Left, Right)
        if eaten or key in D:
            result.pop()
            flag = True

    for boat, X, Y in result:
        if len(boat) == 2:
            boat = ''.join(boat)
        print '%8s' % ''.join(X),
        if 'o' in X:
            s = "|| (%2s) --> ||" % boat
        else:
            s = "|| <-- (%2s) ||" % boat
        print '%18s' % s,
        print '%8s' % ''.join(Y), '\n'

def move_to_another_side(boat, Left, Right):
    Current, OtherSide = Left, Right
    if 'o' not in Current:
        Current, OtherSide = OtherSide, Current
    if not isinstance(boat, (list, tuple)):
        boat = [boat]
    OtherSide.append('o')
    for x in boat:
        OtherSide.append(x)

    for x in boat:
        Current.remove(x)
    Current.remove('o')
    eaten = is_bad(Left) or is_bad(Right)
    Left.sort()
    Right.sort()
    return Left, Right, eaten

if __name__ == "__main__":
    start()