Tower of Hanoi

Animated Tower of Hanoi

By Monty, 3rd July 2015

Tower of Hanoi

By André Karwath aka Aka (Own work) [CC BY-SA 2.5 (http://creativecommons.org/licenses/by-sa/2.5)], via Wikimedia Commons

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)
Wikipedia:

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:

  1. Only one disk can be moved at a time.
  2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
  3. No disk may be placed on top of a smaller disk.

With 3 disks, the puzzle can be solved in 7 moves. The minimal number of moves required to solve a Tower of Hanoi puzzle is 2n − 1, where n is the number of disks.

What do you think?

Leave a Reply

%d bloggers like this: