ハノイの塔

Pythonハノイの塔を解くプログラムを書きました。
GUIの表示にはmatplotlibの棒グラフを使いました。

import numpy as np
import matplotlib.pyplot as plt
import matplotlib.animation as animation

def plot():
    plt.cla()
    plt.xlim(-0.5,2.5)
    plt.ylim(0,N)
    left = np.array([0,1,2])
    numl = [0,0,0]
    plt.bar(left,lis[N-1],color="0.0",linewidth = 0.5)
    numl = lis[N-1]
    for i in (reversed(range(N-1))):
        plt.bar(left,lis[i],bottom=numl,color=str(0.95-0.95*(i/N)),linewidth = 1)
        numl = lisum(numl,lis[i])
    plt.pause(0.3)

def hanoi(num,fro,des,wor):
    if num == 1:
        move(1,des)
        plot()
    else:
        hanoi(num-1,fro,wor,des)
        move(num,des)
        plot()
        hanoi(num-1,wor,des,fro)
def move(n,tar):
    s = [0,0,0]
    s[tar] = 1
    lis[n-1] = s

def lisum(a,b):
    s = []
    for i in range(len(a)):
        s.append(a[i]+b[i])
    return s
fig = plt.figure()
N = int(input())
lis = []
for i in range(N):
    lis.append([1,0,0])
plot()
hanoi(N,0,2,1)

実際にハノイの塔を解くアルゴリズムはこの部分

def hanoi(num,fro,des,wor):
    if num == 1:
        move(1,des)
        plot()
    else:
        hanoi(num-1,fro,wor,des)
        move(num,des)
        plot()
        hanoi(num-1,wor,des,fro)

一見めんどくさそうなゲームに見えるハノイの塔がこれだけのコードで解けるのは驚きです。
def hanoi(int,int,int,int)は、
num...解くハノイの塔のディスクの数
fro...棒の番号を左から0,1,2と振ったときのディスクがnum個ある開始位置の番号
des...num個のディスクを移動させたい棒の番号
wor...操作において利用可能な棒の番号
fro != des != worが成り立ちます。
move(n,des)関数は、n番目のディスク、(小さい方から1..nとしています)をdesに移動させる操作です。
手続きを見ていきます。
基底: num = 1のとき
ディスクが一つのみなので、1のディスクをdesに移動させて終わりです。
帰納: num = nのとき
まずnum-1までのディスクを操作において利用可能な棒、worにすべて移動させます。これは、hanoi(num-1,fro,wor,des)で可能です。
次に、動かせるようになったnum番目のディスクをdesに移動させます。これはmoveの一手で可能です。
最後に、desに移動したnum番目のディスクの上にworに乗っているnum-1個のディスクをのせて終わりです。これはhanoi(num-1,wor,des,fro)で可能です。