The Tower of Hanoi is a classic problem that lends itself well to a recursive solution. The story involves some poor monks having to move 64 disks of different sizes (with central holes for the pegs) from one peg to another. There are three pegs, all the disks started on the first peg (in size order, largest on the bottom), can only be moved one at a time, and have to end up on the third peg. Oh, and no disk may ever be placed on a smaller disk.
The Magic of Recursion
One of the most useful techniques of program design is called recursion. You look to see if your problem can be broken down in such a way that the procedure separates out a ‘smaller’ copy, on which you can apply the procedure again – and again on the smaller part, until the smaller part has reached a limiting case where the solution is trivial. The procedure then unwinds, using the trivial solution to solve the previous case. For example, to compute n!, which is n * (n-1) * (n-2) … * 1, we notice that n! = n * (n-1)! If the program doesn’t know what the value of (n-1)! is, it can try (n-2)! and so on. Then it does the multiplications on the way back…
def factorial(n): if n > 1: return n * factorial(n-1) else: return 1 print(factorial(5))
This suggests that we could try looking at moving (n-1) disks to the next peg, then moving the bottom disk to the destination peg, then moving the original pile of (n-1) disks onto the destination peg. And each move of (n-1) disks can be done likewise by moving (n-2) disks, and so on, till we get down to 1 disk, which can just be moved with no more recursion.
The basic solution in program code is remarkably simple. To arrive at it, imagine you already have a magical ‘hanoi’ program. You could solve the problem if you could ‘hanoi’ all but one of the disks from the first peg to the second, then move that remaining disk over to the third peg, then ‘hanoi’ all the disks on peg 2 to peg 3. Job done! Well, nearly. Before we can ‘hanoi’ the first bunch of disks, we need to ‘hanoi’ all but one of those… So each call to hanoi has to call hanoi on a smaller stack of disks, first to get them off the biggest disk, then to get them back on it once we’ve moved the biggest disk to where we need it. So it looks like this:
def hanoi(ndisks, startPeg, endPeg): if ndisks: hanoi(ndisks-1, startPeg, 3-startPeg-endPeg) print("Move disk",ndisks-1,"to peg",endPeg) hanoi(ndisks-1, 3-startPeg-endPeg, endPeg) hanoi(4,0,2) # 4 disks, from peg 0 to peg 2
The 3-startPeg-endPeg is just a clever little bit of arithmetic that determines which peg to move the disks to; in the beginning it evaluates to 1. The procedure ends when there are no more disks to move. A few lines of code constructed by imagining that you already have a magic function called ‘hanoi’ becomes the magic function itself!
This one is probably my favourite example of a recursive program. It solves a problem with a minimum of fuss, with not even any assignment statements! And if you look at that print() statement between the 2 hanoi() calls – it says “Move disk…” but no actual move takes place here! You could remove it, the program would still work (though of course you wouldn’t know how)! There are no (obvious) data structures keeping track of where the disks are. With a little reflection, we realise that all hanoi() needs to know is how many disks to move from where to where, and that’s all saved in the recursion stack.
Animating it with Pygame
Watching the program print out “Move disk 0 to peg 1, Move disk 1 to peg 2” soon gets old. Wouldn’t it be a lot more fun if we could actually watch the disks in motion? Yes, of course it would! Enter PyGame. It does make the program quite a bit bigger, but the end result is worth it!
The original program changes really only in one line: the print() becomes moveDisk() which performs the animation. We keep things simple by just drawing in elevation, i.e. a ground-level view of the 3 pegs – which we don’t bother to draw, just the disks seen edge-on. And there’s no gravity in Hanoi. When the disks move to another peg, they don’t drop down if there are no disks or the ground under them… It makes life so much easier for the monks!
Note that in the code, disks and pegs are numbered from 0 whereas real people in ‘the real world’ would normally call the first peg ‘number one’ etc. But they don’t have to deal with computers where everything starts from nothing.
''' Animated Tower of Hanoi Graphical display of the moves to solve Tower of Hanoi. Authour: Alan Richmond, Python3.Codes ''' import pygame, time cols = ['#ff0000','#ff8000','#ffff00','#008000','#0000ff','#a000c0'] ndisks = 6 # Number of disks w, h = 1024, 512 # Size of display window st = 0.005 # Animation speen - smaller is faster wx = int(w/6) dh = int(h/ndisks) radius = 60 rect=[0 for i in range(ndisks)] d = pygame.display.set_mode((w,h)) pygame.display.set_caption("Towers of Hanoi") def moveDisk(disk, to): print("Move disk %d to peg %d" % (disk, to)) r = radius*(disk+1) c = pygame.Color(cols[disk]) (x1,_,_,_)=rect[disk] # current position x2=wx+to*2*wx-r/2 # desired position dx = (x2-x1)/50 # step size for i in range(50): # Animation loop: # erase disk from current position pygame.draw.rect(d, pygame.Color('#000000'), rect[disk]) rect[disk]=pygame.Rect(x1+dx*(i+1),dh*disk,r,dh) pygame.draw.rect(d, c, rect[disk]) # draw disk in new position pygame.display.flip() # update display time.sleep(st) # slow it down or it's too fast time.sleep(1) # allow a little time to admire it.. # This is the magic bit: def hanoi(ndisks, startPeg=0, endPeg=2): if ndisks: # move all but 1 disc from 1 peg to other hanoi(ndisks-1, startPeg, 3-startPeg-endPeg) moveDisk(ndisks-1, endPeg) # move 1 disk to vacant peg # now move rest on to it... hanoi(ndisks-1, 3-startPeg-endPeg, endPeg) # Set up initial tower of disks for disk in range(ndisks): r = radius*(disk+1) rect[disk]=pygame.Rect(dx-r/2,dh*disk,r,dh) # save disk coords, size pygame.draw.rect(d, pygame.Color(cols[disk]), rect[disk]) pygame.display.flip() time.sleep(2) hanoi(ndisks)