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.
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)
The Tower of Hanoi (also called the Tower of Brahma or Lucas' Tower, and sometimes pluralized) is a mathematical game or puzzle. It consists of three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.
The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:
With three disks, the puzzle can be solved in seven moves. The minimum number of moves required to solve a Tower of Hanoi puzzle is 2n – 1, where n is the number of disks.