WGC

 # Initial and goal states

initial_state = ("left", {"wolf", "goat", "cabbage", "farmer"}, set())

goal_state = ("right", set(), {"wolf", "goat", "cabbage", "farmer"})

def wgc_solver(boat_position, left_bank, right_bank, path=[]):

    # Check if the goal state is reached

    if (boat_position, left_bank, right_bank) == goal_state:

        for step in path:

            print(step)

        return True

    # Items the farmer can take in the boat (one at a time or alone)

    possible_moves = [None, "wolf", "goat", "cabbage"]

    

    for item in possible_moves:

        # Determine new positions based on the current boat position

        if boat_position == "left":

            new_boat_position = "right"

            new_left_bank = left_bank - {"farmer", item} if item else left_bank - {"farmer"}

            new_right_bank = right_bank | {"farmer", item} if item else right_bank | {"farmer"}

        else:

            new_boat_position = "left"

            new_left_bank = left_bank | {"farmer", item} if item else left_bank | {"farmer"}

            new_right_bank = right_bank - {"farmer", item} if item else right_bank - {"farmer"}

        # Check safety rules

        if "wolf" in new_left_bank and "goat" in new_left_bank and "farmer" not in new_left_bank:

            continue  # Unsafe: wolf and goat together on the left bank

        if "goat" in new_left_bank and "cabbage" in new_left_bank and "farmer" not in new_left_bank:

            continue  # Unsafe: goat and cabbage together on the left bank

        if "wolf" in new_right_bank and "goat" in new_right_bank and "farmer" not in new_right_bank:

            continue  # Unsafe: wolf and goat together on the right bank

        if "goat" in new_right_bank and "cabbage" in new_right_bank and "farmer" not in new_right_bank:

            continue  # Unsafe: goat and cabbage together on the right bank

        # Avoid revisiting states to prevent cycles

        new_state = (new_boat_position, frozenset(new_left_bank), frozenset(new_right_bank))

        if new_state in path:

            continue

        # Recursive call for the next step

        if wgc_solver(new_boat_position, new_left_bank, new_right_bank, path + [new_state]):

            return True

    return False  # No solution found

# Solve the problem starting from the initial state

print("Solution steps:")

wgc_solver("left", {"wolf", "goat", "cabbage", "farmer"}, set())