修道士野人过河问题，Python

修道士野人过河问题是一个经典的算法问题，通常用于讲解回溯法。它描述了一个场景：有若干只修道士和野人在一座独木桥上，每次只能让一个修道士或一个野人过桥，但是每当有奇数数量的修道士在一起时，修道士必须背着一个野人才能过桥。问题是找到一种策略，使得所有的人安全地到达对岸。

在Python中，这个问题可以使用递归函数来解决。首先定义一个状态表示当前有多少个修道士和野人，以及他们分别在那一边。然后编写一个函数，检查是否满足过桥条件，如果不能，则尝试所有的可能性，包括修道士过桥、野人过桥或留在原地。当所有人都到达对岸时，就找到了解决方案。

以下是简化版的Python代码示例：

def monk_crossing(state, monks=0, priests=0, target_monks=1, target_priests=0):
    if (monks, priests) == (target_monks, target_priests):
        print("Solution found:", state)
        return True

    # 尝试所有可能的行动
    for action in [(monks+1, priests), (monks, priests+1), (monks, priests)]:
        if 0 <= action[0] <= target_monks and 0 <= action[1] <= target_priests:
            next_state = (action[0], action[1])
            if monk_crossing(next_state, *action):  # 递归调用
                return True
    return False

# 起始状态，假设一个修道士和一个野人在桥的一侧
start_state = (1, 1, 0, 0)
if not monk_crossing(start_state):
    print("No solution exists.")