Towers of Hanoi solution using a recursive function -- with plots

For a general description of the game, see http://en.wikipedia.org/wiki/Tower_of_Hanoi.



In [ ]:

    
%pylab inline

First version: just print out moves



In [ ]:

    
def move_disks(itop, ibottom, from_peg, to_peg):
    if itop > ibottom:
        raise InputError("Require itop <= ibottom, got itop = %i, ibottom = %i" %(itop,ibottom))
    if itop==ibottom:
        print "Move Disk %i from Peg %i to Peg %i" % (itop, from_peg, to_peg)
    else:
        other_peg = 6 - from_peg - to_peg
        # recursive call:
        move_disks(itop, ibottom-1, from_peg, other_peg)
        move_disks(ibottom, ibottom, from_peg, to_peg)
        move_disks(itop, ibottom-1, other_peg, to_peg)



In [ ]:

    
n = 2
move_disks(1,n,1,3)



In [ ]:

    
n = 3
move_disks(1,n,1,3)

Second version, print out configuration of disks on pegs after each move



In [ ]:

    
n = 3
peg = {}
peg[1] = range(1,n+1)
peg[2] = []
peg[3] = []
def print_pegs():
        print "   Peg 1 holds: ",peg[1]
        print "   Peg 2 holds: ",peg[2]
        print "   Peg 3 holds: ",peg[3]
        
print "Initial configuration:"
print_pegs()
        
def move_disks2(itop, ibottom, from_peg, to_peg):
    if itop > ibottom:
        raise InputError("Require itop <= ibottom, got itop = %i, ibottom = %i" %(itop,ibottom))
    if itop==ibottom:
        print "Move Disk %i from Peg %i to Peg %i" % (itop, from_peg, to_peg)
        peg[from_peg] = peg[from_peg][1:]   # drop first element of list
        peg[to_peg] = [itop] + peg[to_peg]  # add as first element of list
        print_pegs()
    else:
        other_peg = 6 - from_peg - to_peg
        # recursive call:
        move_disks2(itop, ibottom-1, from_peg, other_peg)
        move_disks2(ibottom, ibottom, from_peg, to_peg)
        move_disks2(itop, ibottom-1, other_peg, to_peg)
        
move_disks2(1,n,1,3)

Plotting the configuration

Rather than printing what disks are on each peg, it would be much nicer to draw a figure. Here are a couple functions that might be useful.



In [ ]:

    
def plot_disk(j,n,peg,position):
    """
    plot disk number j out of n (j=1 is the smallest, j=n the largest)
    also specify which peg (1,2, or 3) to plot it on, and its position.
    position=1 means it is on the base, position=2 is on top of one other disk, etc.
    """
    width = j/float(n)  # actually the half-width of the jth disk
    height = 1./float(n)  # so n of them fit between 0 and 1 in y-direction
    xpeg = 1 + 2.5*(peg-1)  # location of this peg (they are at x = 1, 3.5, 7)
    x = [xpeg-width, xpeg+width, xpeg+width, xpeg-width, xpeg-width]
    y0 = (position-1)*height
    y = [y0, y0, y0+height, y0+height, y0]
    fill(x,y,'r')  # fill in a rectangle with red, specified by the 5 (x,y) points
    
def plot_pegs(n):
    plot([0,7],[0,0],'k',linewidth=3)
    plot([1,1],[0,1.2],'k',linewidth=3)
    plot([3.5,3.5],[0,1.2],'k',linewidth=3)
    plot([6,6],[0,1.2],'k',linewidth=3)
    axis([0,7,0,1.5])

Here's an example of plotting one configuration:



In [ ]:

    
n = 4
plot_pegs(n)
for j in range(1,n+1):
    plot_disk(j,n,1,n+1-j)
axis('off')  # comment this line out to see the axes, useful for debugging!

Use the functions above to make a sequence of plots showing the configuration after each move is made.

One possible solution:

First define a function to plot the configuration of all three pegs...



In [ ]:

    
def plot_all_disks(n,peg):
    plot_pegs(n)
    for i in [1,2,3]:
        disks = peg[i]
        for j,disk in enumerate(disks):
            plot_disk(disk,n,i,len(disks)-j)
    show()

Now call this function each time a move is made



In [ ]:

    
n = 4
peg = {}
peg[1] = range(1,n+1)
peg[2] = []
peg[3] = []
        
print "Initial configuration:"
plot_all_disks(n,peg)
        
def move_disks2(itop, ibottom, from_peg, to_peg):
    if itop > ibottom:
        raise InputError("Require itop <= ibottom, got itop = %i, ibottom = %i" %(itop,ibottom))
    if itop==ibottom:
        print "Move Disk %i from Peg %i to Peg %i" % (itop, from_peg, to_peg)
        peg[from_peg] = peg[from_peg][1:]   # drop first element of list
        peg[to_peg] = [itop] + peg[to_peg]  # add as first element of list
        plot_all_disks(n,peg)
        
    else:
        other_peg = 6 - from_peg - to_peg
        # recursive call:
        move_disks2(itop, ibottom-1, from_peg, other_peg)
        move_disks2(ibottom, ibottom, from_peg, to_peg)
        move_disks2(itop, ibottom-1, other_peg, to_peg)
        
move_disks2(1,n,1,3)



In [ ]: