CODEWITHSUNDEEP
pythonrecursiontowers-of-hanoi
ray
ray

Reputation: 671

Understand Python for Towers of Hanoi

I understand the thinking of how to solve Hanoi with Python recursion, but I don’t understand how we could write this Python language:

def hanoi(n,x,y,z):
    if n == 1:
        print(x, ' --> ',z)
    else:
        hanoi(n-1,x,z,y)
        print(x, ' --> ',z)
        hanoi(n-1,y,x,z)
hanoi(2,'SRC','TMP','TAG')

if the first step is to put (x-1) dishes from source to tmp, why we write hanoi(n-1,z,y) ? why we switch z and y?

thanks!

Upvotes: 1

Views: 2165

Answers (1)

mleyfman
mleyfman

Reputation: 635

You are understanding the variables wrong:

  • n is the number of disks
  • x is the first pole
  • y is the pole used for transferring
  • z is the pole for the destination of the transferred disk

Since we want to solve hanoi(n, x, y, z), we do as follows:

  • If there's only 1 disk to move, we're done (aka the n==1 bit)
  • Otherwise we have to move the disk from the source pole (x) to the final pole (z) using the temporary pole (y)

We do this by moving n-1 disks from x to y using z (aka hanoi(n-1, x, z, y)), then moving the last disk to z, then moving all remaining disks (which are on y) onto z (the final pole) with hanoi(n-1, y, x, z)

Here's a gif to illustrate:

enter image description here

Upvotes: 4

Related Questions