Program rozwiązujący zagadkę o misjonarzach i kanibalach dla ich dowolnej liczby oraz dowolnej pojemności łódki.

misjonarze.py

def mutations(state, boat_size):
    m_left, k_left, boat, m_right, k_right = state
    sign, other_side = (-1, "R") if boat == "L" else (1, "L")

    naive_mutations = [
        (m_left + sign * m_diff, k_left + sign * k_diff,
         other_side,
         m_right - sign * m_diff, k_right - sign * k_diff)
        for m_diff in range(boat_size + 1)
        for k_diff in range(boat_size + 1)
        if 1 <= m_diff + k_diff <= boat_size
        if m_diff >= k_diff or m_diff == 0
    ]
    return filter(lambda (a, b, _, x, y): (b >= a == 0 or a >= b >= 0) and
                                          (y >= x == 0 or x >= y >= 0),
                  naive_mutations)


def main(missionaries, cannibals, boat_size):
    start_state = (missionaries, cannibals, "L", 0, 0)
    final_state = (0, 0, "R", missionaries, cannibals)

    states = {start_state}
    ancestors = {start_state: None}

    while True:
        new_states = set(
            (new_state, state)
            for state in states
            for new_state in mutations(state, boat_size)
            if new_state not in states
        )
        if new_states:
            for new_state, ancestor in new_states:
                ancestors[new_state] = ancestor
                states.add(new_state)
        else:
            break

    current = final_state
    solution = [current]

    while ancestors.get(current):
        solution.append(ancestors[current])
        current = ancestors[current]

    return solution[::-1]

if __name__ == "__main__":
    def draw_state(state_to_draw):
        ml, kl, boat, mr, kr = state_to_draw
        left = " ".join(["M"] * ml + ["K"] * kl)
        right = " ".join(["M"] * mr + ["K"] * kr)
        print '{:12s} | {}'.format(left, right)

    solution_path = main(missionaries=3, cannibals=3, boat_size=2)
    for solution_state in solution_path:
        draw_state(solution_state)