(別解) Pythonで川渡り問題「宣教師と人喰い」を解く 【探索的（発見的）プログラム・再帰】

元ネタは @kansihoさんの 「[Pythonで川渡り問題「宣教師と人喰い」を解く 【探索的（発見的）プログラム・再帰】](http://qiita.com/kansiho/items/6cded7436241681caf00)」です。

懐かしいネタで面白そうだったので、自分でも実装してみました。
方針は同じです。手順がひとつ見つかっても終わらずに他の手順も探すようにしました。

宣教師と人喰いのグループを`Group`クラスにして、ボートへの乗降計算処理を加減算でできるようにしました。
往路と復路で処理が異なりますが、`if`文で処理を分けると煩雑になって可読性が下がるので、`forward`関数と`backward`関数に分けました。
往路と復路の処理で共通に必要な「ボートに乗って移動しても安全な(喰われない)乗客の組合せを選び出す処理」を`safe_passengers`関数にしました。
`passengers_combinations`は、「岸に乗客が残っているか」や「ボートに乗って移動しても安全か(喰われないか)」といった条件に関係なく、1人か2人の乗客の組合せ配列です。変化することのない固定データなのでタプルにしました。

実装する際には、
・コメントがなくてもプログラムを理解できる変数名や関数名を付ける
・`if`文や`for`文を多段にしない
ということを意識しました。

```py3
#!/usr/bin/env python3

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 step in steps:
        return
    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))
```

追記
@tanuk1647さん の指摘のおかげで、backwardでも重複チェックが必要なことがわかりました。
手順は、11ステップが4つになりました。
出力結果を横に並べ直した結果がこちら。

```text
bank: (3, 3)>   (0, 0)   bank: (3, 3)>   (0, 0)   bank: (3, 3)>   (0, 0)   bank: (3, 3)>   (0, 0)
BOAT: (0, 2)--->(0, 2)   BOAT: (0, 2)--->(0, 2)   BOAT: (1, 1)--->(1, 1)   BOAT: (1, 1)--->(1, 1)
bank: (3, 1)   <(0, 2)   bank: (3, 1)   <(0, 2)   bank: (2, 2)   <(1, 1)   bank: (2, 2)   <(1, 1)
BOAT: (0, 1)<---(0, 1)   BOAT: (0, 1)<---(0, 1)   BOAT: (1, 0)<---(1, 0)   BOAT: (1, 0)<---(1, 0)
bank: (3, 2)>   (0, 1)   bank: (3, 2)>   (0, 1)   bank: (3, 2)>   (0, 1)   bank: (3, 2)>   (0, 1)
BOAT: (0, 2)--->(0, 2)   BOAT: (0, 2)--->(0, 2)   BOAT: (0, 2)--->(0, 2)   BOAT: (0, 2)--->(0, 2)
bank: (3, 0)   <(0, 3)   bank: (3, 0)   <(0, 3)   bank: (3, 0)   <(0, 3)   bank: (3, 0)   <(0, 3)
BOAT: (0, 1)<---(0, 1)   BOAT: (0, 1)<---(0, 1)   BOAT: (0, 1)<---(0, 1)   BOAT: (0, 1)<---(0, 1)
bank: (3, 1)>   (0, 2)   bank: (3, 1)>   (0, 2)   bank: (3, 1)>   (0, 2)   bank: (3, 1)>   (0, 2)
BOAT: (2, 0)--->(2, 0)   BOAT: (2, 0)--->(2, 0)   BOAT: (2, 0)--->(2, 0)   BOAT: (2, 0)--->(2, 0)
bank: (1, 1)   <(2, 2)   bank: (1, 1)   <(2, 2)   bank: (1, 1)   <(2, 2)   bank: (1, 1)   <(2, 2)
BOAT: (1, 1)<---(1, 1)   BOAT: (1, 1)<---(1, 1)   BOAT: (1, 1)<---(1, 1)   BOAT: (1, 1)<---(1, 1)
bank: (2, 2)>   (1, 1)   bank: (2, 2)>   (1, 1)   bank: (2, 2)>   (1, 1)   bank: (2, 2)>   (1, 1)
BOAT: (2, 0)--->(2, 0)   BOAT: (2, 0)--->(2, 0)   BOAT: (2, 0)--->(2, 0)   BOAT: (2, 0)--->(2, 0)
bank: (0, 2)   <(3, 1)   bank: (0, 2)   <(3, 1)   bank: (0, 2)   <(3, 1)   bank: (0, 2)   <(3, 1)
BOAT: (0, 1)<---(0, 1)   BOAT: (0, 1)<---(0, 1)   BOAT: (0, 1)<---(0, 1)   BOAT: (0, 1)<---(0, 1)
bank: (0, 3)>   (3, 0)   bank: (0, 3)>   (3, 0)   bank: (0, 3)>   (3, 0)   bank: (0, 3)>   (3, 0)
BOAT: (0, 2)--->(0, 2)   BOAT: (0, 2)--->(0, 2)   BOAT: (0, 2)--->(0, 2)   BOAT: (0, 2)--->(0, 2)
bank: (0, 1)   <(3, 2)   bank: (0, 1)   <(3, 2)   bank: (0, 1)   <(3, 2)   bank: (0, 1)   <(3, 2)
BOAT: (0, 1)<---(0, 1)   BOAT: (1, 0)<---(1, 0)   BOAT: (0, 1)<---(0, 1)   BOAT: (1, 0)<---(1, 0)
bank: (0, 2)>   (3, 1)   bank: (1, 1)>   (2, 2)   bank: (0, 2)>   (3, 1)   bank: (1, 1)>   (2, 2)
BOAT: (0, 2)--->(0, 2)   BOAT: (1, 1)--->(1, 1)   BOAT: (0, 2)--->(0, 2)   BOAT: (1, 1)--->(1, 1)
bank: (0, 0)   <(3, 3)   bank: (0, 0)   <(3, 3)   bank: (0, 0)   <(3, 3)   bank: (0, 0)   <(3, 3)
11 steps.                11 steps.                11 steps.                11 steps.
```