Towers of Hanoi - Watch it unfold through recursion!


#1

5-disk Tower here.

When I saw the Towers of Hanoi project, I thought it would have something to do with solving the problem, but it turns out to be a module that allows the user to play the game, via (appropriately) the user-defined “stack” - based data structure. I added a “graphic” add-on, which you can find here, but the interesting stuff is in the solution.

When you study recursion, the examples always given are factorial, fibonacci, and palindromes, all problems that illustrate recursion, but which might generate a bit of “so what?” attitude, since they can all be easily coded iteratively. But the Towers of Hanoi problem provides a superb example of the beauty of recursion, since it provides in an amazingly few lines a solution that, in iterative form, is much more difficult.

I’m not going to go into the explanation, but there is a very nice one here, beginning at 20:20. I have taken the code from that lecture and changed only the order of the parameters to correspond with our “L”, “M” and “R”. I have also replaced the printMove() line with one that actually does the move in our module - to.push(fr.pop()) - then prints out the graphic with a small (optional) delay.

So, to implement this, begin with the module, as modified via the above link to implement ASCII-graphics.

To the top of your module, add

import time
DELAY = 0.5  # delay in seconds

Now, comment out everything after #Play the Game

In its place, paste in the following code:

num_moves = {'n':0}
def towers(n, fr, spare, to):
    if n == 1:
        to.push(fr.pop())
        time.sleep(DELAY)
        print_pix()
        num_moves['n'] += 1
    else:
        towers(n-1, fr, to, spare)
        towers(1, fr, spare, to)
        towers(n-1, spare, fr, to)
        
print_pix()
towers(num_disks, left_stack, middle_stack, right_stack)

num_user_moves = num_moves['n']
print("\n\nI completed the game in {0} moves, and the optimal number of moves is {1}".format(num_user_moves, num_optimal_moves))

Run it as usual. Of course, you can change the delay at the top of the module, 0 = no delay.