start = {"farmer": True, "fox": True, "goose": True, "grain": True}
goal = {"farmer": False, "fox": False, "goose": False, "grain": False}

class Rule0():
    num = 0

    def apply(self, state):
        return {"farmer": not state["farmer"],
                "fox": not state["fox"],
                "goose": state["goose"],
                "grain": state["grain"]}

    def can_apply(self, state):
        return state["farmer"] == state["fox"] and \
               state["goose"] != state["grain"]

    def describe(self):
        print "Farmer moves fox to the opposite bank."

class Rule1():
    num = 1

    def apply(self, state):
        return {"farmer": not state["farmer"],
                "fox": state["fox"],
                "goose": not state["goose"],
                "grain": state["grain"]}

    def can_apply(self, state):
        return state["farmer"] == state["goose"]

    def describe(self):
        print "Farmer moves goose to the opposite bank."

class Rule2():
    num = 2

    def apply(self, state):
        return {"farmer": not state["farmer"],
                "fox": state["fox"],
                "goose": state["goose"],
                "grain": not state["grain"]}

    def can_apply(self, state):
        return state["farmer"] == state["grain"] and \
               state["fox"] != state["goose"]

    def describe(self):
        print "Farmer moves grain to the opposite bank."

class Rule3():
    num = 3

    def apply(self, state):
        return {"farmer": not state["farmer"],
                "fox": state["fox"],
                "goose": state["goose"],
                "grain": state["grain"]}

    def can_apply(self, state):
        return state["fox"] != state["goose"] and \
               state["goose"] != state["grain"]

    def describe(self):
        print "Farmer moves to the opposite bank."

rules = [Rule0(), Rule1(), Rule2(), Rule3()]

def long_print(steps):
    state = start

    for s in steps:
        rules[s].describe()
        state = rules[s].apply(state)

        print "On the left bank: ",                         \
              " ".join(map(lambda (a, b): a,
                           filter(lambda (a, b): b,
                                  state.items()))) +        \
              ("(none)" if not any(state.values()) else "")
        print "On the right bank:",                         \
              " ".join(map(lambda (a, b): a,
                           filter(lambda (a, b): not b,
                                  state.items()))) +        \
              ("(none)" if all(state.values()) else "")
        print

queue = [([], start)]
visited = [start]
steps = 0

while len(queue) > 0:
    path, state = queue[0]
    new_nodes = []

    for rule in rules:
        if rule.can_apply(state):
            n_state, n_path = rule.apply(state), path + [rule.num]

            if n_state == goal:
                print "Solution found in %d iterations:" % steps, n_path
                print
                long_print(n_path)
                exit(0)

            if not any([n_state == s for s in visited]):
                new_nodes.append((n_path, n_state))
                visited.append(n_state)

    queue = new_nodes + queue[1:]   # DFS
    # queue = queue[1:] + new_nodes # BFS

    steps += 1

print "No solution found!"