ハノイの塔は、3本のポールと直径の異なる「n」枚の円盤からなる数学的な問題（パズル）です。
ハノイの塔問題の目的
この問題の目的は，すべての「n」枚の円盤を，元の極から先の極に，前と同じ配置になるように移動させることである．しかし，この目的は，以下の規則に従うことによって達成されなければならない．
ルールと制約事項
問題を解く際に満たさなければならない制約条件は、以下の通りです。
-
- 一度に動かせるディスクは 1 枚だけです。
-
- 一番上のディスクのみを取り外すことができる
- 大きいディスクを小さいディスクの上に置くことはできません。
ハノイの塔のビジュアル表現問題
次の図は，3 つの極 (供給元，中間，供給先) と 3 枚の円板を持つハノイの塔の段階的な解法を示している．目標は，3枚の円盤をすべて極Aから極Cに移動させることである．
def TowerOfHanoi(n , s_pole, d_pole, i_pole):
if n == 1:
print("Move disc 1 from pole",s_pole,"to pole",d_pole)
return
TowerOfHanoi(n-1, s_pole, i_pole, d_pole)
print("Move disc",n,"from pole",s_pole,"to pole",d_pole)
TowerOfHanoi(n-1, i_pole, d_pole, s_pole)
n = 3
TowerOfHanoi(n, 'A', 'C', 'B')
# A, C, B are the name of poles |
上の解答からわかるように、3枚の円盤に必要な移動回数＝8回なので、必要な総移動回数を一般化した式が
総手数＝n2 – 1
ここで、nはディスクの総枚数です。
Pythonでハノイの塔問題を解決する
上のコードでは、関数TowerOfHanoiを3枚のディスクに対して再帰的に呼び出しています。
ここで
- s_pole: 入力極
- i_pole: 中間極
- dttpd: 出力極
上記のコードの出力は以下の通りです。
まとめ
以上がハノイの塔の問題の解き方です。
このコードは、任意の枚数のディスクに対して一般化することができる。
もし、円盤が4枚の場合の解答が欲しければ、n = 4として、nの値を3から4に変更すれば、円盤が4枚の場合の出力が表示され、以下同様です。