https://qiita.com/shiracamus/items/ce536aaad95932dbbfb5

missionaries_and_cannibals.py

#!/usr/bin/env python
# -*- coding:utf-8 -*-

from itertools import product


class Group:

    def __init__(self, missionaries, cannibals):
        self.missionaries = missionaries
        self.cannibals = cannibals

    def __str__(self):              # for "%s" % self
        return "({0.missionaries}, {0.cannibals})".format(self)

    def __add__(self, group):       # "+" operator
        return Group(self.missionaries + group.missionaries, self.cannibals + group.cannibals)

    def __sub__(self, group):       # "-" operator
        return Group(self.missionaries - group.missionaries, self.cannibals - group.cannibals)

    def __contains__(self, group):  # "in" operator
        return self.missionaries >= group.missionaries and self.cannibals >= group.cannibals

    def is_empty(self):
        return self.missionaries == self.cannibals == 0

    def is_safe(self):
        return self.missionaries == 0 or self.missionaries >= self.cannibals


passengers_combinations = tuple(Group(missionaries, cannibals)
                                for missionaries, cannibals in product((0, 1, 2), (0, 1, 2))
                                if missionaries + cannibals in (1, 2))


def safe_passengers(depature_bank, arrival_bank):
    return (passengers
            for passengers in passengers_combinations
            if passengers in depature_bank
            if (depature_bank - passengers).is_safe()
            if (arrival_bank + passengers).is_safe())


def backward(left_bank, right_bank, steps):
    step = 'bank: %s   <%s' % (left_bank, right_bank)
    if left_bank.is_empty():  # Goal
        print('\n'.join(steps + (step,)))
        print('%s steps.\n' % (len(steps) // 2))
        return
    for passengers in safe_passengers(depature_bank=right_bank, arrival_bank=left_bank):
        forward(left_bank + passengers, right_bank - passengers,
                steps + (step, 'BOAT: %s<---%s' % (passengers, passengers)))


def forward(left_bank, right_bank, steps=()):
    step = 'bank: %s>   %s' % (left_bank, right_bank)
    if step in steps:
        return
    for passengers in safe_passengers(depature_bank=left_bank, arrival_bank=right_bank):
        backward(left_bank - passengers, right_bank + passengers,
                 steps + (step, 'BOAT: %s--->%s' % (passengers, passengers)))


if __name__ == '__main__':
    forward(Group(missionaries=3, cannibals=3), Group(missionaries=0, cannibals=0))