n = 3 # n個(gè)傳教士、n個(gè)野人
m = 2 # 船能載m人
x = [] # 一個(gè)解，就是船的一系列狀態(tài)
X = [] # 一組解
is_found = False # 全局終止標(biāo)志
# 計(jì)算船的合法狀態(tài)空間（二維）
def get_states(k): # 船準(zhǔn)備跑第k趟
  global n, m, x
  if k%2==0: # 從左到右，只考慮原左岸人數(shù)
    s1, s2 = n - sum(s[0] for s in x), n - sum(s[1] for s in x)
  else:    # 從右到左，只考慮原右岸人數(shù)（將船的歷史狀態(tài)累加可得！?。。?
    s1, s2 = sum(s[0] for s in x), sum(s[1] for s in x)
  for i in range(s1 + 1):
    for j in range(s2 + 1):
      if 0 < i+j <= m and (i*j == 0 or i >= j):
        yield [(-i,-j), (i,j)][k%2==0]  # 生成船的合法狀態(tài)
# 沖突檢測(cè)
def conflict(k): # 船開(kāi)始跑第k趟
  global n, m, x
  # 若船上載的人與上一趟一樣（會(huì)陷入死循環(huán)！?。。。?
  if k > 0 and x[-1][0] == -x[-2][0] and x[-1][1] == -x[-2][1]:
    return True
  # 任何時(shí)候，船上傳教士人數(shù)少于野人，或者無(wú)人，或者超載（計(jì)算船的合法狀態(tài)空間時(shí)已經(jīng)考慮到了。）
  #if 0 < abs(x[-1][0]) < abs(x[-1][1]) or x[-1] == (0, 0) or abs(sum(x[-1])) > m:
  #  return True
  # 任何時(shí)候，左岸傳教士人數(shù)少于野人
  if 0 < n - sum(s[0] for s in x) < n - sum(s[1] for s in x):
    return True
  # 任何時(shí)候，右岸傳教士人數(shù)少于野人
  if 0 < sum(s[0] for s in x) < sum(s[1] for s in x):
    return True
  return False # 無(wú)沖突
# 回溯法
def backtrack(k): # 船準(zhǔn)備跑第k趟
  global n, m, x, is_found
  if is_found: return # 終止所有遞歸
  if n - sum(s[0] for s in x) == 0 and n - sum(s[1] for s in x) == 0: # 左岸人數(shù)全為0
    print(x)
    is_found = True
  else:
    for state in get_states(k): # 遍歷船的合法狀態(tài)空間
      x.append(state)
      if not conflict(k):
        backtrack(k+1) # 深度優(yōu)先
      x.pop()  # 回溯
# 測(cè)試
backtrack(0)