狼羊草和农夫过河问题

问题描述

农夫需要把狼、羊、菜和自己运到河对岸去，只有农夫能够划船，而且船比较小，除农夫之外每次只能运一种东西，还有一个棘手的问题，就是如果没有农夫看着，羊会偷吃菜，狼会吃羊。请考虑一种方法，让农夫能够安全地安排这些东西和他自己过河。

代码实现

本题使用深度优先策略构建行动树，搭配三种剪枝逻辑以保证结果可行 老婆饿了，要赶回家送饭，细节请读代码，见谅~~

left = 0b1111
right = 0b0000
steps = [0b1000, 0b1001, 0b1010, 0b1100]
wrong = [0b0110, 0b0011]
ever = [right]
path = []

def search_path(left, right, ever, path):
    if right == 0b1111:
        print(path)
        return
    for step in steps:
        if max(left, right) & step != step:
            continue
        left_n = left ^ step
        right_n = right ^ step
        if left_n in wrong or right_n in wrong:
            continue
        if right_n in ever:
            continue
        path_n = path[:]
        path_n.append(step)
        ever_n = ever[:]
        ever_n.append(right_n)
        search_path(left_n, right_n, ever_n, path_n)

search_path(left, right, ever, path)