人狼羊菜过河 python

人狼羊菜过河是一个经典的智力游戏，玩家需要帮助一群人、一只狼、一只羊和一堆菜过河，但船只只能承载两个物品或人。同时，如果没有人看守，羊会被狼吃掉，而如果没有羊吃菜，菜也会被吃掉。因此，玩家需要想出一个方案，让所有物品和人都安全地渡河。

以下是人狼羊菜过河的 Python 实现示例：

# 定义初始状态
start = {'people': 1, 'wolf': 1, 'sheep': 1, 'vegetable': 1, 'boat': 0}
# 定义目标状态
goal = {'people': 0, 'wolf': 0, 'sheep': 0, 'vegetable': 0, 'boat': 1}

# 定义移动函数
def move(state, p, q):
    new_state = state.copy()
    new_state['people'] -= p
    new_state['wolf'] -= q
    new_state['sheep'] += q
    new_state['vegetable'] += p
    new_state['boat'] = 1 - state['boat']
    return new_state

# 定义判断函数
def is_valid(state):
    if state['wolf'] == state['sheep'] and state['people'] != state['wolf']:
        return False
    if state['sheep'] == state['vegetable'] and state['people'] != state['sheep']:
        return False
    return True

# 定义搜索函数
def search(start, goal):
    visited = set()
    queue = [[start]]
    while queue:
        path = queue.pop(0)
        last_state = path[-1]
        if last_state == goal:
            return path
        for p in range(2):
            for q in range(2):
                if p + q == 0 or p + q == 2:
                    continue
                new_state = move(last_state, p, q)
                if is_valid(new_state) and tuple(new_state.items()) not in visited:
                    visited.add(tuple(new_state.items()))
                    new_path = path + [new_state]
                    queue.append(new_path)

# 运行搜索函数并输出结果
result = search(start, goal)
for state in result:
    print(state)