Towers of Hanoi

In [1]:

def hanoi(n,source,helper,target):
    global A,B,C   # this statement not necessary...why not?
    if n==1:       
        target.append(source.pop())
        print A, B, C
    else:
        hanoi(n-1,source,target,helper)
        target.append(source.pop())
        print A, B, C
        hanoi(n-1,helper,source,target)
        
A=[5,4,3,2,1]
B=[]
C=[]
print A, B, C

hanoi(len(A),A,B,C)

[5, 4, 3, 2, 1] [] []
[5, 4, 3, 2] [] [1]
[5, 4, 3] [2] [1]
[5, 4, 3] [2, 1] []
[5, 4] [2, 1] [3]
[5, 4, 1] [2] [3]
[5, 4, 1] [] [3, 2]
[5, 4] [] [3, 2, 1]
[5] [4] [3, 2, 1]
[5] [4, 1] [3, 2]
[5, 2] [4, 1] [3]
[5, 2, 1] [4] [3]
[5, 2, 1] [4, 3] []
[5, 2] [4, 3] [1]
[5] [4, 3, 2] [1]
[5] [4, 3, 2, 1] []
[] [4, 3, 2, 1] [5]
[1] [4, 3, 2] [5]
[1] [4, 3] [5, 2]
[] [4, 3] [5, 2, 1]
[3] [4] [5, 2, 1]
[3] [4, 1] [5, 2]
[3, 2] [4, 1] [5]
[3, 2, 1] [4] [5]
[3, 2, 1] [] [5, 4]
[3, 2] [] [5, 4, 1]
[3] [2] [5, 4, 1]
[3] [2, 1] [5, 4]
[] [2, 1] [5, 4, 3]
[1] [2] [5, 4, 3]
[1] [] [5, 4, 3, 2]
[] [] [5, 4, 3, 2, 1]

Resources¶

• The Towers of Hanoi: Experiential Recursive Thinking | MIT BLOSSOMS

• Proof by induction | Sequences, series and induction | Precalculus | Khan Academy

• Python Tutorial: Towers of Hanoi

• The Tower of Hanoi - and Beyond | Julia Robinson Mathematics Festival