川渡りパズルを解く

川渡りパズルの解答を探すプログラムを書いてみました。
※この記事ではパズルの解答を1つしか求めていませんが、複数の解答が考えられる問題(3.危険な家族)も存在します。

川渡りパズルとは

1. 狼とヤギとキャベツの問題 http://r27.jp/quiz/across-cabbage/

   1匹のオオカミと1匹のヤギを連れ、キャベツを携えた旅人が、舟で川を渡ろうとしている。 舟には、旅人の他に1つのものしか乗せることができない。 ヤギは旅人が近くにいないとキャベツを食べてしまう。 オオカミは旅人が近くにいないとヤギを食べてしまうのである。 全てのものを無事に向こう岸に渡すには、どうすればよいだろうか?

2. 宣教師と先住民の問題 http://r27.jp/quiz/across-or-die/

   3人の宣教師と3人の人喰い人種が、舟で川を渡ろうとしている。 舟は1艘しかないが、1度に2人まで乗ることができ、誰でも漕ぐことが可能である。 ただし、それぞれの岸において、人喰い人種の数が宣教師の数を上回ると、宣教師は食べられてしまう。 さて、全員が無事に川を渡り切るには、どうすればよいだろうか?

3. 危険な家族の問題 http://r27.jp/quiz/across-family/

   ある家族が、舟で川を渡ろうとしている。 家族は父、母、長男、次男、長女、次女、メイド、犬の8人であり、 舟は1艘しかないが、1度に2人まで乗ることができる。 また、舟を漕げるのは父、母、メイドの3人だけである。 ただしこの家族、実はとても危険な家族なのである。 まず父は、母が近くにいないと娘たちをいじめてしまう。 また母は、父が近くにいないと息子たちをいじめてしまう。 そして犬は、メイドが近くにいないと家族全員に襲い掛かってしまうのである。 さて、全員が無事に川を渡り切るには、どうすればよいだろうか?

解き方、考え方

1. ルールで禁止されていない選択肢を幅優先探索
2. ゴール(全員が川を渡り切る)すると解答
3. 同じ局面に戻ってくるのは手数の無駄なので、各局面の左岸の状態とその直前の左岸の状態を記録しておき、過去に現れた局面を拒否する
4. queueを使っているので一番初めに現れた解答が最短であることは確か

実装

banはそれぞれのタプルの第一項のメンバー全てが第二項のメンバー全てと異なる岸に居てはいけないという制約。

import queue
import itertools


def leftover(all_items, remove_items):
    leftover_items = []
    for i in all_items:
        if i not in remove_items:
            leftover_items.append(i)
    return leftover_items

LEFT = 0
RIGHT = 1

characters = sorted(['man', 'wolf', 'goat', 'cabbage', 'boat'])
left_side = sorted(['man', 'wolf', 'goat', 'cabbage', 'boat'])
# everybody in the left side of rever
right_side = sorted([])
# nobady in the right side of rever
rowers = ['man']
# the man only can row the boat
boat_size = 2
ban = [(['man'], ['wolf', 'goat']), (['man'], ['goat', 'cabbage'])]
# wolf eat goat if no man with them, goat eat cabbage if no man with them.
goal = [[], sorted(['man', 'wolf',  'goat', 'cabbage', 'boat'])]
Q = queue.Queue()
past = dict()
Q.put((left_side[:], right_side[:], ['start']))
while not Q.empty():
    q = Q.get()
    if tuple(q[LEFT]) in past:
        continue
    else:
        past.update({tuple(q[LEFT]): q[2]})
    if q[LEFT] == goal[LEFT] and q[RIGHT] == goal[RIGHT]:
        path = []
        t = q[LEFT]
        while t != ['start']:
            path.append(t)
            t = past[tuple(t)]
        path.reverse()
        for p in path:
            print(p, leftover(characters, p))
        exit()

    boat = RIGHT
    if 'boat' in q[LEFT]:
        boat = LEFT
    for rower in rowers:
        if rower in q[boat]:
            for passengers in itertools.combinations([''] * (boat_size - 1) + q[boat], boat_size - 1):
                if rower in passengers or 'boat' in passengers:
                    continue
                left = q[LEFT][:]
                right = q[RIGHT][:]
                if boat == LEFT:
                    left.remove('boat')
                    right.append('boat')
                    if rower != '':
                        left.remove(rower)
                        right.append(rower)
                    for passenger in passengers:
                        if passenger != '':
                            left.remove(passenger)
                            right.append(passenger)
                else:
                    right.remove('boat')
                    left.append('boat')
                    if rower != '':
                        right.remove(rower)
                        left.append(rower)
                    for passenger in passengers:
                        if passenger != '':
                            right.remove(passenger)
                            left.append(passenger)
                is_banned = False
                for b in ban:
                    if (all(c in left for c in b[0]) and all(c in right for c in b[1])) or
                       (all(c in left for c in b[1]) and all(c in right for c in b[0])):
                        is_banned = True
                if not is_banned:
                    Q.put((sorted(left[:]),
                           sorted(right[:]), sorted(q[LEFT][:])))
print('no answer')

dictはlistをキーにできない、タプルは必ず複数個の要素が必要という点にハマりました。 他の問題を解いたコードはgithubにあげてあります。(所要時間3時間) github.com