Trouble understanding python code for Towers of Hanoi

Question

NOTE: I have 2 images that I want to post, but I don't have enough reputation: one is the code output and the other is a simple graphic that better defines how this course defined this Towers of Hanoi of problem.

Thanks for the rep so that I can now post images. I have posted an image of the code's output to give you a better idea of this particular formulation of the Towers of Hanoi problem that was presented in this course. Furthermore, I hope it helps those who wish to answer for this specific case if this case is different from the previous answers for Towers of Hanoi questions.

As I mentioned in other posts, I am learning programming mainly for my hobbies. A month or so ago, I decided to stop where I was at learning C and Java and to start learning from the ground up so to speak. So I found some online courseware that teaches programming using Python 2-7. So far, the course is doing well to provide me with a foundation that I need.

I am currently on the topic of recursion in the course and one of the problems that the class used as an example is the Towers of Hanoi problem. I am having some trouble understanding how the recursion is working in this problem. I did not have trouble with understanding how the recursion worked in other examples that the class covered such as the Fibonacci sequence and a palindrome checker.

For reference, I have posted a graphic below of how the Towers of Hanoi problem was formulated for this example:

Since I cannot post an image of how the problem was formulated for this class, I will describe it in text.

n rings start on pole called From and labeled 'f' in the code
Target pole is labeled 't' in code
Spare pole is labeled 's' in code

The two rules for solving the problem are: 1) only 1 ring can be moved at a time and 2) a larger diameter ring cannot be placed on top of a smaller diameter ring.

Working this out by hand, I determined the solutions below:

For n = 2 rings
move f to s
move f to t
move s to t

And below for n = 3 rings:

move f to t
move f to s
move t to s
move f to t
move s to f
move s to t
move f to t

Below is a graphic of the python code used to solve this problem on the right and the output in the shell on the left:

def Hanoi(n,f,t,s,indent = '   '):
    print indent, 'Hanoi called with n = ' + str(n)
    ##print n
    if n == 1:
        print indent, 'move from ' + f + ' to ' + t
    else:
        Hanoi(n-1,f,s,t,indent+indent)
        print indent, 'here'
        Hanoi(1,f,t,s,indent+indent)
        print indent, 'there'
        Hanoi(n-1,s,t,f,indent+indent)
        print indent, 'anywhere'

In the code, the professor mentioned that it was a good idea to use print statements and indents to try to help one better understand how the recursion is working. That strategy helped me to better understand the Fibonacci and palindrome examples, but I am still having trouble with this problem.

Code Output:

As you can see in the output, the move sequences for both n=2 and n=3 agree with the "by-hand solution". I think I understand how the output for n=2 was generated by the code... For n=3 however, I am struggling. Specifically for code in green bracket A, I don't understand how "move from t to s" is the output. I don't see anywhere in the code how "t" can be the first output in that print statement! Similarly for the code in green bracket B, I don't see how "s" can be the first output and "f" the second output in that printed move statement...

I'd appreciate any input that can help me better understand how the recursion is working to solve this problem.

Jorge Plaza Jorge Plaza · Accepted Answer · 2016-05-07T14:56:38

The link provided by Rahn should help you, nevertheless here are my comments regarding your concerns:

Include the labels of the From, Target and Spare poles in the first print statement. That should help you recognize what's happening.
```
print '{0}Hanoi called with n = {1}. Moving from "{2}" to "{3}", using "{4}" as spare'.format(indent, n, f, t, s)
```
Note that there are 3 steps when it's not the base case (n=1), and they call the Hanoi function with smaller instances of the problem (n=n-1 and n=1):

1) Solves the n-1 problem using F as the from, S as the target and T as the spare. This step will leave the n-th (the largest for this recursion step) ring on F and the other (n-1) rings in S.

2) Solves the base case (n=1) using F and T as the from and target. This step moves the n-th ring (the largest) from F to T.

3) Solves the n-1 problem using S as the from, T as the target and F as the spare. This step will move all the rings that were left on S on the first step to T. At the end of this step, the n rings originally on S, are placed on T.

Trouble understanding python code for Towers of Hanoi

2 Answers