ハノイの塔：tkinterアニメーションで人間の試行のように見せる
再起呼び出しだけどバックトラックではないアルゴリズムで解く
Python3(3.10)で動くソースコード（.pyファイル .ipynbファイル）あります
「anaconda3」on .py「PyCharm」.ipynb「Jupyter Notebook」
実際に動く Python ソースコードがあります。ドラッグして開発環境にコピペすればそのまま動きます。Tkinterによるアニメーションで見ればコンピュータの試行が人間の思考のように見えます。
◆◆ハノイの塔◆◆
Wikipedia「ハノイの塔」より
3本の杭と、中央に穴の開いた大きさの異なる複数の円盤から構成される。
最初はすべての円盤が左端の杭に小さいものが上になるように順に積み重ねられている。
円盤を一回に一枚ずつどれかの杭に移動させることができるが、小さな円盤の上に大きな円盤を乗せることはできない。
n枚の円盤すべてを移動させるには最低 2**n - 1 回の手数がかかる。
3本の杭と、中央に穴の開いた大きさの異なる複数の円盤から構成される。
最初はすべての円盤が左端の杭に小さいものが上になるように順に積み重ねられている。
円盤を一回に一枚ずつどれかの杭に移動させることができるが、小さな円盤の上に大きな円盤を乗せることはできない。
n枚の円盤すべてを移動させるには最低 2**n - 1 回の手数がかかる。
（2023-11-14）Python3.10で動作確認済み
◆◆ソースファイル◆◆
このWebの左上隅からダウンロードできます。
ソースファイルは2つあります。「Hanoi_sol.py」では，解答を配列で書いてあります。メインプログラム「Hanoi.py」に import されるので名称はそのままにして同じディレクトリに置きます。
◆◆パズル「ハノイの塔」は再帰呼び出しの代表◆◆
巻末のソースコード「Hanoi_sol.py」の18行目からのわずか5行の関数で解答を出しています。
ところで，再帰呼び出しで有名なものの１つにバックトラックがあります。「ハノイの塔」はバックトラックではありません。
このサイトにバックトラックアルゴリズムの再帰呼び出しを組み込んだ例があります。
https://yamakatsusan.web.fc2.com/hp_software/python05.html
『８人の女王 再帰呼び出しとバックトラックのアルゴリズム Python3で動くソースコードあります』
また，バックトラックの考え方をアニメーションにした例もあります。
https://yamakatsusan.web.fc2.com/hp_software/python06.html
『８人の女王のパズルをPython3で解く Tkinterによるアニメーションの試行が人間思考と同じ』
こちらの方はバックトラックの再帰呼び出しを使っていません。それはTkinterのアニメーションで再帰呼び出しを使っているので二重に再帰呼び出しを使えないからです。それでも再帰呼び出しを使わずバックトラックの考え方を実現しています。
「ハノイの塔」も非再帰でも実現できるのですが，再帰呼び出しの勉強という意味もあり，無理やり再帰呼び出しを使います。
最初の7手で3枚の円盤がきれいに揃うので手順を確認すると機械的手順で円盤を移しているのが判ります。それを巻末のソースの20行目と22行目の再帰呼び出しで実現しています。本来，3つの塔で円盤をやりとりするのですが，自分と相手の塔の番号を3から引くことによって残りの塔の番号を表現しています。
アニメーション描画プログラム「Hanoi.py」にいっぺんに解答を渡すために関数を二重 nesting にして外側の関数の26行目のreturn文で全解答を返しています。28行目以降は単体で run させるときのお決まりの書き方であり，import されたときは28行目以降は runしません。単体の debug のときに run します。
最初の状態
4手目
7手目
◆◆Tkinterによるアニメーション◆◆
Python のアニメーションのライブラリはいくつかあるらしいが，そのうち Tkinter がいいらしい（まったくのうけうり）。
Tkinter によるアニメーション以外の図のつくり方は次のサイトをマネさせてもらった。
http://www.shido.info/py/tkinter9.html
『9. ボードゲーム用 GUI を作ろう 』
アニメーションのつくり方は上のWebにはないのでこのサイトの最初に紹介した別記事を参照してください。
アニメーションには2つの方法があって，1つ目はこのサイトの「8人の女王」のように図を移動していく方法です。図に識別番号を付ける必要があります。2つ目はこのサイトの「マイクロマウス」のように図の数が決まっていなく任意に描画したり消去したりする方法です。
「ハノイの塔」が図（円盤）の数が決まっていますが，後者の描画・消去の方法を採用します。というのは，解答が「何番目の円盤を何番目の塔から何番目の塔へ移す」という指示なので円盤の元の位置を記録しないで円盤を識別番号で消去することができるからです。no 番目の円盤を
tags = hex(no) + hex(no)
のようにタグを自動発行しています。hex が1つだと文字と認識しないようです。tags がないと発行順に識別番号が付くようです。
アニメーション描画プログラム「Hanoi.py」は2つの class からできています。1つは親クラスが「Tkinter.Canvas」であり，もう1つはは親クラスが「Tkinter.Frame」です。
前者の class に54行目に円盤を描画する関数 put_a_disk() があります。これに移動を支持するのが73行目の関数 refresh() です。これを再帰呼び出しするのが後者の class の117行目の関数 show_next() です。この構造はこのサイトの Tkinter を使っているアニメーションプログラムで同じです。
アニメーションのコマ送り間隔は，14行目で設定できる。1以上を設定すること。単位はミリ秒であるが「1」に設定しても描画のためかそれほど速くない。この設定は125行目で関数 show_next() が関数 refresh() を再帰呼び出ししているときの遅れ時間です。1秒（設定は1000）以上にすると試行に人間の思考が追い付いて行けます。
127行目以降は Tkinter を使うときのお決まりのコードです。
余談ですが，数式のプロットする点が動くというアニメーションはまた別の手法を使います。ヒントを言うと，matplotlib.animation の ArtistAnimation または FuncAnimation という関数を使います。
◆◆ソースコード◆◆
このWebの左上隅からダウンロードできます。
ソースファイルは2つあります。
・Hanoi.py.py；描画プログラム（メインプログラム：次をインポートする）
・Hanoi_sol.py；ハノイの塔の解法
「Hanoi_sol.py」では，解答を配列で書いてあります。メインプログラム「Hanoi.py」に import されるので名称はそのままにして同じディレクトリに置きます。
【Hanoi.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
# -*- coding: utf-8 -*-
"""
Tower of Hanoi
"""
import tkinter as Tk
import Hanoi_sol as Ha
Thk_disk = 20
Rad_disk = 20
X00 = 150
Y00 = Thk_disk * 7
Span = 220
disk_color = '#999999'
Timer = 1000 # ミリ秒；アニメーションのコマ送り間隔（1以上を設定）：推奨は1500
class Tower(Tk.Canvas):
"""Tk.Canvas for Tower
"""
cell_size = 46
margin = 5
q_images = []
disk_fig = []
def __init__(self, master):
"""コンストラクタ
"""
cwidth = 3.35 * Span
cheight = Y00 + Thk_disk * 2
"""親コンストラクタ"""
Tk.Canvas.__init__(self, master, relief=Tk.RAISED, bd=4, bg='white',
width=cwidth, height=cheight)
"""解をいっぺんに読み込む"""
self.sol = Ha.solution()
# print self.sol
"""set initial value"""
self.No_disk = [5, 0, 0] # 各塔にある円盤の数
"""地面の描画"""
self.create_rectangle( \
20, Y00, cwidth-20, Y00+20, fill='#666666', width=0, \
tags=(hex(0)+hex(0))
)
"""5枚の円盤の描画（ディフォルトは左の塔）"""
for i in range(5):
x0, y0, x1, y1 = self.coord_disk(1,i+1,5-i)
self.disk_fig.append( \
self.create_rectangle ( \
x0, y0, x1, y1, fill=disk_color, \
width=0, tags=(hex(5-i)+hex(5-i)) \
)
)
"""コンストラクタ終"""
def put_a_disk(self, xg, yg, id):
"""draw a disk
"""
self.delete(hex(id)+hex(id))
x0, y0, x1, y1 = self.coord_disk(xg, yg, id)
self.create_rectangle( \
x0, y0, x1, y1, fill=disk_color, \
width=0, tags=(hex(id)+hex(id)) \
)
def coord_disk(self, xg, yg, id):
"""xg番の塔の下から位置yg番目のid番の円盤
"""
x0 = X00 - Rad_disk * id + Span * (xg - 1)
x1 = X00 + Rad_disk * id + Span * (xg - 1)
y0 = Y00 - Thk_disk * (yg - 1)
y1 = Y00 - Thk_disk * yg
return x0, y0, x1, y1
def refresh(self, No_step):
"""円盤を移す
"""
if self.sol[No_step+1][0] ==0: # ゴールの判定
return True
xb = self.sol[No_step+1][1]
xa = self.sol[No_step+1][2]
id = self.sol[No_step+1][0]
self.No_disk[xb - 1] -= 1
self.No_disk[xa - 1] += 1
self.put_a_disk(xa, self.No_disk[xa - 1], id)
return False
class Hanoi(Tk.Frame):
""" Tk.Frame class of Hanoi """
def __init__(self, master=None):
"""コンストラクタ
creating Hanoi canvas
"""
"""親コンストラクタ"""
Tk.Frame.__init__(self, master)
self.master.title("Tower of Hanoi")
# title
l_title = Tk.Label( \
self, text='Tower of Hanoi', \
font=('Times', '24', ('italic', 'bold')),
fg='#191970', bg='#EEE8AA', width=12
)
l_title.pack(padx=10, pady=10)
# canvas
self.TowerCanvas = Tower(self)
self.TowerCanvas.pack(padx=10, pady=10)
# buttons and a counter
self.No_step = 0
self.f_footer = Tk.Frame(self)
self.f_footer.pack()
self.a_button = Tk.Button( \
self.f_footer, text="start", font=("Times", 14), \
command = self.show_next \
)
self.a_button.pack(side=Tk.LEFT, padx=5,pady=5)
"""コンストラクタ終"""
def show_next(self):
"""アニメーションのコマ送り
"""
sol = self.TowerCanvas.refresh(self.No_step)
if sol:
"""解発見"""
return
self.No_step += 1
self.after(Timer, self.show_next)
if __name__ == "__main__":
app = Hanoi()
app.pack()
app.mainloop()
【Hanoi_sol.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
# -*- coding: utf-8 -*-
"""
Solution of Tower of Hanoi
"""
"""
sol[] = [A, B, C] の意味
A 番の円盤をB 番の塔からC 番の塔へ移す。
円盤は最小が1番，最大が5番，塔は左が1番，右が3番とする。
hanoi(X, Y, Z)関数の引数の意味
X 枚の円盤が最初 Y+1 番目の塔にありそれを全部 Z+1 番目の塔に移す。
描画プログラムはそれを読み取らないのでバグります。
このプログラム単体で確認してください。
"""
def solution():
No_tower = 3 # 塔の数
sol = [[]] # 円盤を移す手順
def hanoi(n, before, after):
if n > 0:
hanoi(n - 1, before, No_tower - (before + after))
sol.append([n, before+1, after+1])
hanoi(n - 1, No_tower - (before + after), after)
hanoi(5,0,2)
sol.append([0,0,0])
return sol
if __name__ == '__main__':
print(solution())