宣教師と人食い人種：再帰呼び出しとバックトラックのアルゴリズム
Python3(3.10)で動くソースコード（.pyファイル .ipynbファイル）あります
「anaconda3」on .py「PyCharm」.ipynb「Jupyter Notebook」
◆◆パズル「宣教師と人食い人種」◆◆
３人の宣教師と３人の人食い人種が，２人しか乗れないボートで河を渡ろうとしています。
こちら岸でも向こう岸でも，宣教師が人食い人種より少なくなると食われてしまいます。
全員無事に向こう岸にうまく渡る方法を考えて下さい。
こちら岸でも向こう岸でも，宣教師が人食い人種より少なくなると食われてしまいます。
全員無事に向こう岸にうまく渡る方法を考えて下さい。
（2023-11-14）Python3.10で動作確認済み
◆◆宣教師と人食い人種を解くには人工知能言語が必要◆◆
これらの問題を人工知能言語 Prolog（プロローグ）で解くと10行程度のプログラムですむらしい。ここでは，Prologの書き方を学ぶのではなく，Python のような手続き型言語を使って，再帰呼び出しとバックトラックのアルゴリズムを学びたい。
このアルゴリズムをプログラムすると新しいプログラミング言語を開発できたかのような錯覚におちいる。それほどすばらしいアルゴリズムである。
◆◆再帰呼び出しとは◆◆
再帰呼び出し（recursive call）とは，次のようなものである。
・自分で自分を定義する
・自分が自分を呼び出す
簡単な例として階乗がある。次のように階乗を階乗で定義しているのである。
N ! = N×(N-1) !
これをプログラムすると，N ! を計算している途中で(N-1) ! の計算が始まることになる。単純にサブルーチンが自分を読んでしまうと計算途中のデータが破壊されてしまう。
これを解決するには，サブルーチンを再入可能（reentrant）な構造にすればよい。
再入可能な再帰呼び出しとバックトラックが実際にどのような構造になるのかはアルゴリズムの中で説明する。
◆◆バックトラック・アルゴリズム◆◆
１．イニシャライズする ２．ＣＡＬＬ ＳＵＢ（１番目のステップ） ３．ＥＮＤ ＳＵＢ（Ｎ番目のステップ） １．ＷＨＩＬＥ 方法がまだある Ａ．次の方法を探す Ｂ．ＩＦ その方法が可能なら ＴＨＥＮ １．その方法を実行する ２．ＩＦ ゴールに達したなら ＴＨＥＮ Ａ．解を出力する ３．ＥＬＳＥ Ａ．ＣＡＬＬ ＳＵＢ ４．その方法を取り消す ２．ＲＥＴＵＲＮ
命令文の簡単な説明は次である（特定の言語と関係ない）。
ＣＡＬＬ文はサブルーチンコールである。ＳＵＢは再入可能とする。ＷＨＩＬＥ文は，条件が満足すればループする（このプログラムではＲＥＴＵＲＮ文の前まで）。ＩＦ ＴＨＥＮ ＥＬＳＥ文は，条件が満足か否かにより分岐する。
下から３行目に再帰呼び出しがある。
再帰呼び出しするためには，再入可能でなければならない。
これを実現するために，もう少し詳細なアルゴリズムを説明する。
◆◆「宣教師と人食い人種」の詳細アルゴリズム◆◆
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
Main 宣教師と人食い人種
イニシャライズ
Gosub BoatOnRiver
End Main
Sub BoatOnRiver:
W=1
While W <= 5:
Wによりボートに乗る組合せを選択
試行の計算
If 試行が成功するなら Then
仮に実行する
If 仮の実行の結果宣教師が食われないなら Then
次のステップの準備
If 全員が渡ったなら Then
解を出力
Else
Stackに保存する
Stack Pointer１増
Gosub BoatOnRiver
次のステップがもうなく戻ってきた
試行を取り消す
W=W+1
Else
Stackがまだ残っていれば
Stack Pointer１減
Stackから戻す
Return
再帰的ＣＡＬＬ文は18～20行目で，再帰的ＲＥＴＵＲＮ文は25～27行目で実現している。ＷＨＩＬＥ文が終わるとＥＬＳＥ文が実行される。
７行目の変数 W は試行方法である。
「宣教師と人食い人種」では，ボートに乗る組み合わせである。
ループの先頭で，ある方法を試行し，成功すればさらに再帰的に試行し，失敗すればその試行を破棄しループの先頭に戻る。これを繰り返すのである。
ある試行が成功しかつ問題全体が成功したら解を出力する。
実際のコードは巻末を見てください。
◆◆「宣教師と人食い人種」の解◆◆
巻末の Python のソースコードをドラッグして開発環境にコピペしてrunさせればよい。解ごとに解を表示して一時停止する。「ENTER」をタイプすれば次の解の計算が始まる。解は4つある。
同じパズルを Excel VBA（エクセル ヴィービーエイ）でも解いてある。下の図は Excel VBA で解いたものであり，アニメの停止図である。この Excel は左上隅よりダウンロードできる。 Excel を起動すれば，プログラムは自動的に run する。
こちらの方は，人間の思考のように，ボートに乗る組合せを試行する過程をアニメで表示している。アニメを見ているとまるで人工知能ではなく生身の人間がパズルを解いているように見える。
そちらの方で解いた４つの解のうち１例を示す。
◆◆「宣教師と人食い人種」の Python のソースコードと４つの解◆◆
次がPython のソースコードである。ドラッグして開発環境にコピペしてrunさせることができる。上に詳細アルゴリズムを表示しているので改めて説明は不要であろう。
試行過程（思考過程？）の途中を知りたい場合は，51行目の文頭のコメントを外し98行目の関数Progressのコメントアウトを外してください。
デバッグ用などで詳細のパラメータの推移を確認したい場合は，98行目の関数Progressの代わりに104行目の関数Progressのコメントアウトを外してください。そして137～139行目の文頭のコメントを外すと主要なパラメータをソースファイルと同じディレクトリにファイルで外部出力します。パラメータを詳細に見ていくことによりプログラムの動きが把握できます。
◆◆ソースコード◆◆
このWebページの左上隅からダウンロードできます。
ソースファイルは2つです。
・3missionaries3cannibals3X.py；宣教師と人食い人種の解法（Python3）
・missionariescannibals.xls；同上の Excel VBA 版
【3missionaries3cannibals3X.py】
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144
1
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# Missionaries and Cannibals
import numpy as np
import sys
def BoatOnRiver():
"""メインなサブルーチン
"""
global Way, Num, StackWay, StackPointer, BoatGoing, Old, NumDebug
global MissNear, CannNear, MissOppo, CannOppo, MissBoat, CannBoat
Way = 1
while Way <= 5:
# ボートに乗る組み合わせを順に選択して試みる
if Way == 1:
MissBoat[Num] = 0
CannBoat[Num] = 1
elif Way == 2:
MissBoat[Num] = 1
CannBoat[Num] = 0
elif Way == 3:
MissBoat[Num] = 1
CannBoat[Num] = 1
elif Way == 4:
MissBoat[Num] = 2
CannBoat[Num] = 0
elif Way == 5:
MissBoat[Num] = 0
CannBoat[Num] = 2
else:
MissBoat[Num] = 0
CannBoat[Num] = 0
# 仮にこちら岸と向こう岸の人数を算出する
BoatGoing[Num] = Num % 2
if BoatGoing[Num] == 1: # ボートは往路
MissNear[Num] = MissNear[Num-1] - MissBoat[Num]
CannNear[Num] = CannNear[Num-1] - CannBoat[Num]
MissOppo[Num] = MissOppo[Num-1] + MissBoat[Num]
CannOppo[Num] = CannOppo[Num-1] + CannBoat[Num]
else: # ボートは復路
MissNear[Num] = MissNear[Num-1] + MissBoat[Num]
CannNear[Num] = CannNear[Num-1] + CannBoat[Num]
MissOppo[Num] = MissOppo[Num-1] - MissBoat[Num]
CannOppo[Num] = CannOppo[Num-1] - CannBoat[Num]
if (MissNear[Num] >= 0) and (MissNear[Num] <= 3) and \
(CannNear[Num] >= 0) and (CannNear[Num] <= 3):
# ボートに乗ることができたなら宣教師が食われるか確認する
NumDebug += 1
# Progress(Num) # 途中経過を表示する
NotOld = Old[MissNear[Num]][CannNear[Num]][BoatGoing[Num]] == 0
if NotEaten(Num) and NotOld:
# 宣教師が食われなかったら次のステップ進む
Old[MissNear[Num]][CannNear[Num]][BoatGoing[Num]] = 1
Num += 1
if MissNear[Num - 1] == 0 and CannNear[Num - 1] == 0:
Solution(Num) # 解を発見
print(input(u'解を発見')) # python2 : raw_input
else:
# 次のステップに進める
StackWay[StackPointer] = Way
StackPointer += 1
BoatOnRiver() # recursiveなcall
# 次のステップがもうなく戻ってきた
Num -= 1
Old[MissNear[Num]][CannNear[Num]][BoatGoing[Num]] = 0
# 同じステップでボートに乗る次の組み合わせを試みる準備
Way = Way + 1
# while文の終了
else: # while文の終了後に実行
# recursiveなreturn
StackPointer
if StackPointer != 1:
StackPointer -= 1
Way = StackWay[StackPointer]
def Solution(Num):
"""解を表示
"""
print(' Num Near Boat Opposite')
print(' M C M C M C')
for n in range(0, Num * 2 - 1):
if n % 2 == 0:
# ボートから下りた結果
nn = n // 2 # python2 : nn = n / 2
print('{0:02d} {1:02d} {2:1d} {3:1d} {4:1d} {5:1d}' \
.format(n, nn, MissNear[nn], CannNear[nn],MissOppo[nn], CannOppo[nn]))
else:
if n % 4 == 1:
# 往路のボートに乗る
print('{0:02d} {1:1d} {2:1d} >' \
.format(n, MissBoat[nn + 1], CannBoat[nn + 1]))
else:
# 復路のボートに乗る
print('{0:02d} < {1:1d} {2:1d} ' \
.format(n, MissBoat[nn + 1], CannBoat[nn + 1]))
def Progress(n):
"""途中経過を表示
"""
print('%02d'%n, MissNear[n], CannNear[n], MissBoat[n], \
CannBoat[n], MissOppo[n], CannOppo[n])
def Progress(n):
"""debug用：途中でパラメータを出力
"""
value = '%02d'%n, MissNear[n], CannNear[n], MissBoat[n], \
CannBoat[n], MissOppo[n], CannOppo[n], Way, \
'%02d'%n, '%02d'%NumDebug, Old
s = repr(value) + '\n'
f = open("debug.txt","a")
f.write(s)
f.close
def NotEaten(Num):
"""宣教師が人食い人種に食われるかを確認する
"""
return (MissNear[Num] == 0) or (MissNear[Num] == 3) or \
(MissNear[Num] == CannNear[Num])
# Initialize
Num = 1 # 渡河の回数
NumDebug = 0 # 渡河の試行回数（debug用）
MissNear = [3 for col in range(30)] # こちら岸の宣教師
CannNear = [3 for col in range(30)] # こちら岸の人食い人種
MissOppo = [0 for col in range(30)] # 向こう岸の宣教師
CannOppo = [0 for col in range(30)] # 向こう岸の人食い人種
MissBoat = [0 for col in range(30)] # ボートの宣教師
CannBoat = [0 for col in range(30)] # ボートの人食い人種
BoatGoing = [0 for col in range(30)]# 往路;1，復路;0
# 過去の試行パターンの記録
Old = [[[0 for i in range(2)] for j in range(4)]for k in range(4)]
Old[3][3][0] = 1 # [MissNear][CannNear][BoatGoing]
StackWay=[0 for col in range(30)] # スタック
StackPointer = 1 # スタックポインタ
# f = open("debug.txt","w") # 途中経過のパラメータをファイル出力
# f.write("debug\n")
# f.close()
BoatOnRiver() # メインなサブルーチンを呼ぶ
print(u'これですべての試行が終了')
次がこのプログラムが表示する4つの解です。123行目以降の変数を表示しています。こちら岸と向こう岸の人数は試行の結果を表示しています。
アニメを見たければ上で紹介した Excel VBA の方で見られます。
Num Near Boat Opposite
M C M C M C
00 00 3 3 0 0
01 1 1 >
02 01 2 2 1 1
03 < 1 0
04 02 3 2 0 1
05 0 2 >
06 03 3 0 0 3
07 < 0 1
08 04 3 1 0 2
09 2 0 >
10 05 1 1 2 2
11 < 1 1
12 06 2 2 1 1
13 2 0 >
14 07 0 2 3 1
15 < 0 1
16 08 0 3 3 0
17 0 2 >
18 09 0 1 3 2
19 < 0 1
20 10 0 2 3 1
21 0 2 >
22 11 0 0 3 3
Num Near Boat Opposite
M C M C M C
00 00 3 3 0 0
01 1 1 >
02 01 2 2 1 1
03 < 1 0
04 02 3 2 0 1
05 0 2 >
06 03 3 0 0 3
07 < 0 1
08 04 3 1 0 2
09 2 0 >
10 05 1 1 2 2
11 < 1 1
12 06 2 2 1 1
13 2 0 >
14 07 0 2 3 1
15 < 0 1
16 08 0 3 3 0
17 0 2 >
18 09 0 1 3 2
19 < 1 0
20 10 1 1 2 2
21 1 1 >
22 11 0 0 3 3
Num Near Boat Opposite
M C M C M C
00 00 3 3 0 0
01 0 2 >
02 01 3 1 0 2
03 < 0 1
04 02 3 2 0 1
05 0 2 >
06 03 3 0 0 3
07 < 0 1
08 04 3 1 0 2
09 2 0 >
10 05 1 1 2 2
11 < 1 1
12 06 2 2 1 1
13 2 0 >
14 07 0 2 3 1
15 < 0 1
16 08 0 3 3 0
17 0 2 >
18 09 0 1 3 2
19 < 0 1
20 10 0 2 3 1
21 0 2 >
22 11 0 0 3 3
Num Near Boat Opposite
M C M C M C
00 00 3 3 0 0
01 0 2 >
02 01 3 1 0 2
03 < 0 1
04 02 3 2 0 1
05 0 2 >
06 03 3 0 0 3
07 < 0 1
08 04 3 1 0 2
09 2 0 >
10 05 1 1 2 2
11 < 1 1
12 06 2 2 1 1
13 2 0 >
14 07 0 2 3 1
15 < 0 1
16 08 0 3 3 0
17 0 2 >
18 09 0 1 3 2
19 < 1 0
20 10 1 1 2 2
21 1 1 >
22 11 0 0 3 3
これですべての試行が終了