野人传教士问题

问题描述：
从前有一条河，河的左岸有m个传教士(Missionary)和m个野人(Cannibal)，和一艘最多可乘n人的小船。约定左岸，右岸和船上或者没有传教士，或者野人数量少于传教士，否则野人会把传教士吃掉。

在我的实现中设定了n＝2。

def ferry(s, p, q):
    global _his, _t
    _t = []
    _his = [ (p, s[0], s[1]) ]
    _ferry(p, s[0], s[1], q, 0, 0)

def _ferry(p, a, b, q, x, y):
    if len(_his) % 2 == 0 and x == y == 0:
        _prt()
        return
    for m, n in _comp(a, b):
        if _push_f(m, n, p, a-m, b-n, q, x+m, y+n):
            _ferry(q, x+m, y+n, p, a-m, b-n)
            _pop_f()

def _push_f(m, n, p, a, b, q, x, y):
    if 0 < a < b or 0 < x < y or (q, x, y) in _his:
        return False
    _his.append( (q, x, y) )
    _t.append( (m, n) )
    return True

def _pop_f():
    _his.pop()
    _t.pop()

def _comp(m, n):
    i = 0
    while i <= m and i <= 2:
        j = 0
        while j <= n and j <= 2:
            if 0 < i + j <= 2:
                yield i, j
            j += 1
        i += 1

def _prt():
    u, v = '--(%d,%d)->', '<-(%d,%d)--'
    for x, y in _t:
        print u % (x, y)
        u, v = v, u
    print '--------------------done', _his[0]

for x in (2,2), (3,3), (4,4):
    ferry( x, 'east', 'west' )

--(0,2)->
<-(0,1)--
--(2,0)->
<-(0,1)--
--(0,2)->
--------------------done ('east', 2, 2)
--(0,2)->
<-(0,1)--
--(2,0)->
<-(1,0)--
--(1,1)->
--------------------done ('east', 2, 2)
--(1,1)->
<-(1,0)--
--(2,0)->
<-(0,1)--
--(0,2)->
--------------------done ('east', 2, 2)
--(1,1)->
<-(1,0)--
--(2,0)->
<-(1,0)--
--(1,1)->
--------------------done ('east', 2, 2)
--(0,2)->
<-(0,1)--
--(0,2)->
<-(0,1)--
--(2,0)->
<-(1,1)--
--(2,0)->
<-(0,1)--
--(0,2)->
<-(0,1)--
--(0,2)->
--------------------done ('east', 3, 3)
--(0,2)->
<-(0,1)--
--(0,2)->
<-(0,1)--
--(2,0)->
<-(1,1)--
--(2,0)->
<-(0,1)--
--(0,2)->
<-(1,0)--
--(1,1)->
--------------------done ('east', 3, 3)
--(1,1)->
<-(1,0)--
--(0,2)->
<-(0,1)--
--(2,0)->
<-(1,1)--
--(2,0)->
<-(0,1)--
--(0,2)->
<-(0,1)--
--(0,2)->
--------------------done ('east', 3, 3)
--(1,1)->
<-(1,0)--
--(0,2)->
<-(0,1)--
--(2,0)->
<-(1,1)--
--(2,0)->
<-(0,1)--
--(0,2)->
<-(1,0)--
--(1,1)->
--------------------done ('east', 3, 3)