「嫉妬深い夫の問題」は「川渡りの問題」と呼ばれる古典的なパズルの一種です。このパズルにはたくさんのバリエーションがありますが、その中で「農夫と山羊と狼とキャベツの問題」や「宣教師と先住民」というパズルが有名です。それでは問題です。
二組の夫婦が川を渡ることになりました。ボートには二人しか乗ることができません。どの夫も嫉妬深く、彼自身が一緒にいない限り、ボートでも岸でも妻が他の男といることを許しません。なお、四人ともボートをこぐことができます。この条件で、二組の夫婦が川を渡る最短手順を考えてください。
この問題は「農夫と山羊と狼とキャベツの問題」よりも簡単です。気分転換や息抜きにちょっと考えてみてください。これでは簡単すぎて面白くないという方は、夫婦を三組に増やしてみてください。ぐっと難しくなりますよ。
それではプログラムを作ります。今回は「幅優先探索」で解いてみましょう。使用するプログラミング言語は Python3 (ver 3.8.10) です。最初に定数を定義します。次のリストを見てください。
リスト : 定数の定義
# 定数
Boat = 0x01
Ha = 0x02
Wa = 0x04
Hb = 0x08
Wb = 0x10
Hc = 0x20
Wc = 0x40
Hd = 0x80
Wd = 0x100
Mens = Ha | Hb | Hc | Hd
All2 = 0x1f
All3 = 0x7f
All4 = 0x1ff
# 夫婦
hw2 = [(Ha, Wa), (Hb, Wb)]
# 名前
name = ['Boat', 'Ha', 'Wa', 'Hb', 'Wb', 'Hc', 'Wc', 'Hd', 'Wd']
# ボートに乗る組み合わせ
riders2 = [
Ha, Wa, Hb, Wb,
Ha | Hb, Wa | Wb, Ha | Wa, Hb | Wb
]
今回のプログラムは夫婦とボートをビットで定義して、局面を整数値で表すことにします。夫婦を三組と四組に増やすことを考慮してデータを定義しています。先頭が H の名前が夫、W の名前が妻を表します。ボートに乗る組み合わせは、二人 (二組の夫婦、男性二人、女性二人) で乗る場合と一人で乗る場合があるので、合計で 8 通りになります。これをリスト riders2 で定義します。
次は、岸が安全な状態かチェックする関数 is_safe() を作ります。
リスト : 安全確認
def is_safe(side, ps):
for h, w in ps:
if side & w > 0 and side & Mens > 0 and side & h == 0:
return False
return True
is_safe() の引数 side が岸を表します。引数 ps には夫婦を表すデータ hw2 を渡します。ps から一組の夫婦 h, w を取り出します。side に女性 w がいる場合、他の男性がいるのに自分の夫がいないと安全ではありません。return で False を返します。すべての夫婦の安全を確認したら、最後に return で True を返します。
次はボートを動かす手順を生成する関数 make_move() を作ります。
リスト : ボートを動かす手順を生成する
def make_move(left, right, riders):
move = []
for x in riders:
y = Boat | x
if left & y == y or right & y == y:
move.append((left ^ y, right ^y))
return move
make_move() の引数 left, right は左岸と右岸の状態を表し、riders にはボートに乗る組み合わせを渡します。ボートに乗る人を順番に取り出して変数 x にセットし、そこに Boat を追加して変数 y にセットします。left & y が y と等しい、または right & y が y と等しい場合、ボートに乗って移動することができます。リスト move に新しい状態 (left ^ y, right ^ y) を追加します。最後に return で move を返します。
次は幅優先探索でパズルを解く関数 bfs2() を作ります。
リスト : 幅優先探索 (二組の問題)
def bfs2():
queue = [[(All2, 0)]]
while len(queue) > 0:
moves = queue.pop(0)
left, right = moves[-1]
for l, r in make_move(left, right, riders2):
if is_safe(l, hw2) and is_safe(r, hw2) and (l, r) not in moves:
xs = moves[:]
xs.append((l, r))
if r == All2:
print_moves(xs)
return
else:
queue.append(xs)
このプログラムでは左岸から右岸へ渡ることにします。リスト queue をキューとして使います。queue の要素は移動手順を表すリストです。リストにタプル (左岸の状態, 右岸の状態) を格納して移動手順を表します。queue の先頭要素は [(All2, 0)] に初期化します。
最初の while ループで、キューにデータがある間は幅優先探索を続けます。次に、pop(0) でキューから手順を一つ取り出して変数 moves にセットします。moves の末尾要素が現在の状態になります。それを変数 left, right にセットします。make_move() でボートを動かして新しい状態 l, r を生成します。is_safe() で l と r の安全を確認し、(l, r) が moves になければ、(l, r) へ移動することができます。
moves をコピーして変数 xs にセットし、その末尾に (l, r) を追加します。そして、r が All2 と等しければ、全員が右岸へ渡ることができました。print_moves() で移動手順を表示し、return で探索を終了します。そうでなければ、xs を queue に追加して探索を続けます。
あとは特に難しいところはないでしょう。詳細はプログラムリストをお読みくださいませ。
それでは実行結果を示します。
>>> bfs2() [ Boat Ha Wa Hb Wb ] [ ] [ Ha Hb ] [ Boat Wa Wb ] [ Boat Ha Wa Hb ] [ Wb ] [ Wa ] [ Boat Ha Hb Wb ] [ Boat Ha Wa ] [ Hb Wb ] [ ] [ Boat Ha Wa Hb Wb ]
0: [ Boat Ha Wa Hb Wb ] [ ] 1: [ Ha Hb ] [ Boat Wa Wb ] 2: [ Boat Ha Wa Hb ] [ Wb ] 3: [ Wa ] [ Boat Ha Hb Wb ] 4: [ Boat Ha Wa ] [ Hb Wb ] 5: [ ] [ Boat Ha Wa Hb Wb ]
5 手で解くことができました。実はこの問題、プログラムを作らなくても簡単に解くことができます。
最初にボートに乗るとき、1 人では意味が無いので必ず 2 人で乗ることになります。まず最初 (1 回目) に Ha と Wa がボートに乗って右岸へ渡ることにします。すると、2 回目は Ha が戻ることになります。Wa が戻ると左岸で Hb と一緒になるからです。3 回目は Ha と Hb が渡ります。Hb と Wb が渡ると右岸で Wa と Hb が一緒になってしまいます。この段階で左岸には Wb が残っているので、4 回目で Hb が戻って、5 回目で一緒に渡ればいいわけです。
ちなみに、このパズルは条件を「夫婦でない男女が二人きりになってはいけない」に変更すると、最初に Ha と Hb が渡っても解くことができます。
0: [ Boat Ha Wa Hb Wb ] [] 1: [ Wa Wb ] [ Boat Ha Hb ] 2: [ Boat Ha Wa Wb ] [ Hb] 3: [ Wb ] [ Boat Ha Wa Hb ] 4: [ Boat Hb Wb ] [ Ha Wa] 5: [] [ Boat Ha Wa Hb Wb ]
最初に Ha と Hb が渡って Ha が戻ってきても、2: のように左岸では Wa が居るので、Ha と Wb の 2 人きりにはなりません。この場合も 5 回で解くことができます。
実は、条件が何もない場合でも、最短手数は 5 回かかります。ボートには 2 人しか乗ることができないので、1 往復で 1 人しか運ぶことができません。2 往復で 2 人を送り込み、最後に 2 人が渡る手順が最短手数となります。3 組の夫婦の場合、何も条件がないと 4 往復＋ 1 回の 9 回が最短手数になりますが、残念ながら 9 回で解くことはできません。最短手数が何回になるか、息抜きや気分転換に考えてみてください。
次は夫婦を三組に増やしてみましょう。
三組の夫婦が川を渡ることになりました。ボートには二人しか乗ることができません。どの夫も嫉妬深く、彼自身が一緒にいない限り、ボートでも岸でも妻が他の男といることを許しません。なお、六人ともボートをこぐことができます。この条件で、三組の夫婦が川を渡る最短手順を考えてください。
それではプログラムを作りましょう。最初にデータを定義します。
リスト : データの定義
# 夫婦
hw3 = hw2 + [(Hc, Wc)]
# ボートに乗る組み合わせ
riders3 = [
Ha, Wa, Hb, Wb, Hc, Wc,
Ha | Hb, Ha | Hc, Hb | Hc,
Wa | Wb, Wa | Wc, Wb | Wc,
Ha | Wa, Hb | Wb, Hc | Wc
]
三組の夫婦を (Ha, Wa), (Hb, Wb), (Hc, Wc) とし、変数 hw3 にセットします。ボートに乗る組み合わせは全部で 15 通りになります。これを変数 riders3 にセットします。
あとは幅優先探索を行う関数 bfs3() を作るだけです。
リスト : 幅優先探索 (三組)
def bfs3():
queue = [[(All3, 0)]]
while rc < len(queue):
moves = queue.pop(0)
left, right = moves[-1]
for l, r in make_move(left, right, riders3):
if is_safe(l, hw3) and is_safe(r, hw3) and (l, r) not in moves:
xs = moves[:]
xs.append((l, r))
if r == All3:
print_moves(xs)
return
else:
queue.append(xs)
queue の先頭要素は [(All3, 0)] に初期化します。make_move() を呼び出すときは riders3 を渡すことと、is_safe() には hw3 を渡すことに注意してください。あとは bfs2() と同じです。
それでは実行結果を示します。最短手数は 11 手で、次のようになります。
>>> bfs3() [ Boat Ha Wa Hb Wb Hc Wc ] [ ] [ Ha Hb Hc Wc ] [ Boat Wa Wb ] [ Boat Ha Wa Hb Hc Wc ] [ Wb ] [ Ha Hb Hc ] [ Boat Wa Wb Wc ] [ Boat Ha Wa Hb Hc ] [ Wb Wc ] [ Ha Wa ] [ Boat Hb Wb Hc Wc ] [ Boat Ha Wa Hb Wb ] [ Hc Wc ] [ Wa Wb ] [ Boat Ha Hb Hc Wc ] [ Boat Wa Wb Wc ] [ Ha Hb Hc ] [ Wc ] [ Boat Ha Wa Hb Wb Hc ] [ Boat Wa Wc ] [ Ha Hb Wb Hc ] [ ] [ Boat Ha Wa Hb Wb Hc Wc ]
0: [ Boat Ha Wa Hb Wb Hc Wc ] [ ] 1: [ Ha Hb Hc Wc ] [ Boat Wa Wb ] 2: [ Boat Ha Wa Hb Hc Wc ] [ Wb ] 3: [ Ha Hb Hc ] [ Boat Wa Wb Wc ] 4: [ Boat Ha Wa Hb Hc ] [ Wb Wc ] 5: [ Ha Wa ] [ Boat Hb Wb Hc Wc ] 6: [ Boat Ha Wa Hb Wb ] [ Hc Wc ] 7: [ Wa Wb ] [ Boat Ha Hb Hc Wc ] 8: [ Boat Wa Wb Wc ] [ Ha Hb Hc ] 9: [ Wc ] [ Boat Ha Wa Hb Wb Hc ] 10: [ Boat Wa Wc ] [ Ha Hb Wb Hc ] 11: [ ] [ Boat Ha Wa Hb Wb Hc Wc ]
ちなみに、この問題は「ボートをこぐことができる女性が 1 人しかいない」という条件でも解くことができます。ボートの乗り手が「こぐことができない人だけ」にならないよう riders3 を修正するだけです。たとえば、ボートをこぐことができる女性を Wa とすると、最短手順は次のようになります。
0: [ Boat Ha Hb Hc Wa Wb Wc ] [] 1: [ Ha Hc Wa Wc ] [ Boat Hb Wb ] 2: [ Boat Ha Hb Hc Wa Wc ] [ Wb ] 3: [ Ha Hb Hc ] [ Boat Wa Wb Wc ] 4: [ Boat Ha Hb Hc Wa ] [ Wb Wc ] 5: [ Ha Wa ] [ Boat Hb Hc Wb Wc ] 6: [ Boat Ha Hb Wa Wb ] [ Hc Wc ] 7: [ Hb Wb ] [ Boat Ha Hc Wa Wc ] 8: [ Boat Hb Hc Wb Wc ] [ Ha Wa ] 9: [ Wb Wc ] [ Boat Ha Hb Hc Wa ] 10: [ Boat Wa Wb Wc ] [ Ha Hb Hc ] 11: [ Wc ] [ Boat Ha Hb Hc Wa Wb ] 12: [ Boat Hc Wc ] [ Ha Hb Wa Wb ] 13: [] [ Boat Ha Hb Hc Wa Wb Wc ]
最短手数は 13 手になります。ところで、夫婦が四組に増えると、二人乗りのボートで川を渡ることはできません。三人乗りのボートにするか、川の中に小島がひとつあれば二人乗りのボートでも渡ることができます。次は四組の嫉妬深い夫の問題に挑戦してみましょう。
それでは、夫婦を四組に増やします。
四組の夫婦が川を渡ることになりました。川の中には小島がひとつあり、何人でもそこに立つことができます。ただし、ボートには二人しか乗ることができません。どの夫も嫉妬深く、彼自身が一緒にいない限り、ボートでも岸でも小島でも、妻が他の男といることを許しません。なお、八人ともボートをこぐことができます。この条件で、四組の夫婦が川を渡る最短手順を考えてください。
この問題は川の中にある小島を利用しないと解くことができません。すぐに思い付く手順は、最初に一組の夫婦を小島に移し、それから三組の夫婦を対岸に渡し、最後に小島にいる夫婦をつれてくる、というものです。この手順では岸と小島の往復に 4 回ずつかかるので、手数は合計で 19 回になります。手順の一例を示します。
左岸 小島 右岸
0 : [Boat Ha Hb Hc Hd Wa Wb Wc Wd] [] []
1 : [Ha Hb Hc Wa Wb Wc] [Boat Hd Wd] []
2 : [Boat Ha Hb Hc Hd Wa Wb Wc] [Wd] []
3 : [Hb Hc Hd Wb Wc] [Wd] [Ha Wa Boat]
4 : [Boat Ha Hb Hc Hd Wb Wc] [Wd] [Wa]
5 : [Hb Hc Wb Wc] [Boat Ha Hd Wd] [Wa]
6 : [Boat Ha Hb Hc Wb Wc] [Hd Wd] [Wa]
7 : [Ha Hb Hc] [Hd Wd] [Boat Wa Wb Wc]
8 : [Boat Ha Hb Hc Wa] [Hd Wd] [Wb Wc]
9 : [Ha Wa] [Hd Wd] [Boat Hb Hc Wb Wc]
10 : [Boat Ha Hc Wa Wc] [Hd Wd] [Hb Wb]
11 : [Wa Wc] [Hd Wd] [Boat Ha Hb Hc Wb]
12 : [Boat Wa Wb Wc] [Hd Wd] [Ha Hb Hc]
13 : [Wa] [Hd Wd] [Boat Ha Hb Hc Wb Wc]
14 : [Wa] [Boat Ha Hd Wd] [Hb Hc Wb Wc]
15 : [Wa] [Wd] [Boat Ha Hb Hc Hd Wb Wc]
16 : [Wa] [Boat Hd Wd] [Ha Hb Hc Wb Wc]
17 : [Wa] [] [Boat Ha Hb Hc Hd Wb Wc Wd]
18 : [Boat Ha Wa] [] [Hb Hc Hd Wb Wc Wd]
19 : [] [] [Boat Ha Hb Hc Hd Wa Wb Wc Wd]
ところが、これよりも短い手順が存在します。プログラムを作って確かめてみましょう。
最初にデータを定義します。次のリストを見てください。
リスト : データの定義
# 夫婦
hw4 = hw3 + [(Hd, Wd)]
# ボートに乗る組み合わせ
riders4 = [
Ha, Hb, Hc, Hd, Wa, Wb, Wc, Wd,
Ha | Hb, Ha | Hc, Ha | Hd, Hb | Hc, Hb | Hd, Hc | Hd,
Wa | Wb, Wa | Wc, Wa | Wd, Wb | Wc, Wb | Wd, Wc | Wd,
Ha | Wa, Hb | Wb, Hc | Wc, Hd | Wd
]
四組の夫婦を (Ha, Wa), (Hb, Wb), (Hc, Wc), (Hd, Wd) とし、変数 hw4 にセットします。ボートに乗る組み合わせは全部で 24 通りになります。これを変数 riders4 にセットします。
次はボートを動かす手順を生成する関数 make_move4() を作ります。
リスト : 移動手順の生成
def make_move4(left, center, right):
move = []
for x in riders4:
y = Boat | x
if left & y == y:
move.append((left ^ y, center ^ y, right))
move.append((left ^ y, center, right ^ y))
elif center & y == y:
move.append((left ^ y, center ^ y, right))
move.append((left, center ^ y, right ^ y))
elif right & y == y:
move.append((left, center ^ y, right ^ y))
move.append((left ^ y, center, right ^ y))
return move
make_move4() は make_move() に小島の処理を追加するだけです。引数 left, center, right が左岸、小島、右岸の状態を表します。ボートに乗る組み合わせは riders4 から求めます。left & y が y と等しい場合、左岸からボートに乗って移動します。この場合、小島と右岸に行く二通りの手順を生成することに注意してください。小島と右岸からボートに乗る場合も同様です。
最後に、幅優先探索で解を求める関数 bfs4() を作ります。
リスト : 幅優先探索 (四組)
def bfs4():
queue = [[(All4, 0, 0)]]
check = {}
check[(All4, 0, 0)] = True
while len(queue) > 0:
moves = queue.pop(0)
left, center, right = moves[-1]
for l, c, r in make_move4(left, center, right):
k = (l, c, r)
if is_safe(l, hw4) and is_safe(c, hw4) and is_safe(r, hw4) and k not in check:
xs = moves[:]
xs.append(k)
if r == All4:
print_moves4(xs)
return
else:
queue.append(xs)
check[k] = True
リスト queue をキューとして使うのは今までと同じです。変数 check には同一局面のチェックで使用する Python の辞書をセットします。今までは手順 moves の中で同一局面をチェックしていましたが、それだと時間がかかります。
幅優先探索の場合、手数 を 1 つずつ増やしながら探索を行います。このため、n 手目の移動で作られた局面が n 手以前の局面で出現している場合、n 手より短い手数で到達する移動手順が必ず存在します。最短手順を求めるのであれば、この n 手の手順を探索する必要はありません。check をチェックして新しい局面だけキューに登録します。
それから、移動手順の生成は make_move4() を呼び出して、is_safe() には hw4 を渡します。あとは特に難しいところはないでしょう。詳細はプログラムリストをお読みくださいませ。
それでは実行結果を示します。最短手順は 16 手で、次のようになります。
>>> bfs4() [ Boat Ha Wa Hb Wb Hc Wc Hd Wd ] [ ] [ ] [ Ha Hb Hc Wc Hd Wd ] [ Boat Wa Wb ] [ ] [ Boat Ha Wa Hb Hc Wc Hd Wd ] [ Wb ] [ ] [ Ha Hb Hc Hd Wd ] [ Wb ] [ Boat Wa Wc ] [ Boat Ha Wa Hb Hc Hd Wd ] [ Wb ] [ Wc ] [ Ha Wa Hd Wd ] [ Wb ] [ Boat Hb Hc Wc ] [ Boat Ha Wa Hb Hd Wd ] [ Wb ] [ Hc Wc ] [ Hb Hd Wd ] [ Wb ] [ Boat Ha Wa Hc Wc ] [ Hb Hd Wd ] [ Boat Wa Wb ] [ Ha Hc Wc ] [ Boat Hb Wb Hd Wd ] [ Wa ] [ Ha Hc Wc ] [ Wb Wd ] [ Wa ] [ Boat Ha Hb Hc Wc Hd ] [ Wb Wd ] [ Boat Ha Wa ] [ Hb Hc Wc Hd ] [ Wb Wd ] [ ] [ Boat Ha Wa Hb Hc Wc Hd ] [ Boat Wa Wb Wd ] [ ] [ Ha Hb Hc Wc Hd ] [ Wd ] [ ] [ Boat Ha Wa Hb Wb Hc Wc Hd ] [ Boat Hd Wd ] [ ] [ Ha Wa Hb Wb Hc Wc ] [ ] [ ] [ Boat Ha Wa Hb Wb Hc Wc Hd Wd ]
左岸 小島 右岸
0: [ Boat Ha Wa Hb Wb Hc Wc Hd Wd ] [ ] [ ]
1: [ Ha Hb Hc Wc Hd Wd ] [ Boat Wa Wb ] [ ]
2: [ Boat Ha Wa Hb Hc Wc Hd Wd ] [ Wb ] [ ]
3: [ Ha Hb Hc Hd Wd ] [ Wb ] [ Boat Wa Wc ]
4: [ Boat Ha Wa Hb Hc Hd Wd ] [ Wb ] [ Wc ]
5: [ Ha Wa Hd Wd ] [ Wb ] [ Boat Hb Hc Wc ]
6: [ Boat Ha Wa Hb Hd Wd ] [ Wb ] [ Hc Wc ]
7: [ Hb Hd Wd ] [ Wb ] [ Boat Ha Wa Hc Wc ]
8: [ Hb Hd Wd ] [ Boat Wa Wb ] [ Ha Hc Wc ]
9: [ Boat Hb Wb Hd Wd ] [ Wa ] [ Ha Hc Wc ]
10: [ Wb Wd ] [ Wa ] [ Boat Ha Hb Hc Wc Hd ]
11: [ Wb Wd ] [ Boat Ha Wa ] [ Hb Hc Wc Hd ]
12: [ Wb Wd ] [ ] [ Boat Ha Wa Hb Hc Wc Hd ]
13: [ Boat Wa Wb Wd ] [ ] [ Ha Hb Hc Wc Hd ]
14: [ Wd ] [ ] [ Boat Ha Wa Hb Wb Hc Wc Hd ]
15: [ Boat Hd Wd ] [ ] [ Ha Wa Hb Wb Hc Wc ]
16: [ ] [ ] [ Boat Ha Wa Hb Wb Hc Wc Hd Wd ]
かなり複雑な手順になりましたね。一組の夫婦を小島に退避するよりも、女性を一人だけ小島に退避させた方が短い手数になるとはちょっと驚きました。
#
# husband.py : 嫉妬深い夫の問題
#
# Copyright (C) 2022 Makoto Hiroi
#
# 定数
Boat = 0x01
Ha = 0x02
Wa = 0x04
Hb = 0x08
Wb = 0x10
Hc = 0x20
Wc = 0x40
Hd = 0x80
Wd = 0x100
Mens = Ha | Hb | Hc | Hd
All2 = 0x1f
All3 = 0x7f
All4 = 0x1ff
# 夫婦
hw2 = [(Ha, Wa), (Hb, Wb)]
hw3 = hw2 + [(Hc, Wc)]
hw4 = hw3 + [(Hd, Wd)]
# 名前
name = ['Boat', 'Ha', 'Wa', 'Hb', 'Wb', 'Hc', 'Wc', 'Hd', 'Wd']
# ボートに乗る組み合わせ
riders2 = [
Ha, Wa, Hb, Wb,
Ha | Hb, Wa | Wb,
Ha | Wa, Hb | Wb
]
riders3 = [
Ha, Wa, Hb, Wb, Hc, Wc,
Ha | Hb, Ha | Hc, Hb | Hc,
Wa | Wb, Wa | Wc, Wb | Wc,
Ha | Wa, Hb | Wb, Hc | Wc
]
riders4 = [
Ha, Hb, Hc, Hd, Wa, Wb, Wc, Wd,
Ha | Hb, Ha | Hc, Ha | Hd, Hb | Hc, Hb | Hd, Hc | Hd,
Wa | Wb, Wa | Wc, Wa | Wd, Wb | Wc, Wb | Wd, Wc | Wd,
Ha | Wa, Hb | Wb, Hc | Wc, Hd | Wd
]
# 安全確認
def is_safe(side, ps):
for h, w in ps:
if side & w > 0 and side & Mens > 0 and side & h == 0:
return False
return True
# 移動
def make_move(left, right, riders):
move = []
for x in riders:
y = Boat | x
if left & y == y or right & y == y:
move.append((left ^ y, right ^y))
return move
def make_move4(left, center, right):
move = []
for x in riders4:
y = Boat | x
if left & y == y:
move.append((left ^ y, center ^ y, right))
move.append((left ^ y, center, right ^ y))
elif center & y == y:
move.append((left ^ y, center ^ y, right))
move.append((left, center ^ y, right ^ y))
elif right & y == y:
move.append((left, center ^ y, right ^ y))
move.append((left ^ y, center, right ^ y))
return move
# 移動手順の表示
def print_side(side):
print('[', end= ' ')
for i, n in enumerate(name):
if side & (1 << i) != 0:
print(n, end=' ')
print(']', end= ' ')
def print_moves(moves):
for l, r in moves:
print_side(l)
print_side(r)
print()
print()
def print_moves4(moves):
for l, c, r in moves:
print_side(l)
print_side(c)
print_side(r)
print()
print()
#
# 二組の問題
#
def bfs2():
queue = [[(All2, 0)]]
while len(queue) > 0:
moves = queue[rc]
left, right = moves[-1]
for l, r in make_move(left, right, riders2):
if is_safe(l, hw2) and is_safe(r, hw2) and (l, r) not in moves:
xs = moves[:]
xs.append((l, r))
if r == All2:
print_moves(xs)
return
else:
queue.append(xs)
#
# 三組の問題
#
def bfs3():
queue = [[(All3, 0)]]
while rc < len(queue):
moves = queue.pop(0)
left, right = moves[-1]
for l, r in make_move(left, right, riders3):
if is_safe(l, hw3) and is_safe(r, hw3) and (l, r) not in moves:
xs = moves[:]
xs.append((l, r))
if r == All3:
print_moves(xs)
return
else:
queue.append(xs)
#
# 四組の問題
#
def bfs4():
queue = [[(All4, 0, 0)]]
check = {}
check[(All4, 0, 0)] = True
while len(queue) > 0:
moves = queue.pop(0)
left, center, right = moves[-1]
for l, c, r in make_move4(left, center, right):
k = (l, c, r)
if is_safe(l, hw4) and is_safe(c, hw4) and is_safe(r, hw4) and k not in check:
xs = moves[:]
xs.append(k)
if r == All4:
print_moves4(xs)
return
else:
queue.append(xs)
check[k] = True