Solution path for 'Towers of Hanoi'

gistfile1.py

"""Solve 'Towers of Hanoi'"""
import pylab as p;
import mpl_toolkits.mplot3d.axes3d as p3;

def solve(g,n):
    X = [sum(g[0])]
    Y = [sum(g[1])]
    Z = [sum(g[2])]

    moved = 0
    # The process used will take 2**n - 1 moves. 
    # (Usually proved by induction in discrete math courses).
    for i in range(2**n - 1):
        ## First find a tile that one is allowed to move. ##
        # Make a list of the top tile in every stack.
        tops = [a[0] for a in g]
        movable = False
        j = 0
        # Search over the tops until one finds a legal move.
        while not movable:
            # Tiles are only placed on tiles with different parity.
            # We only need the size the largest candidate for now.
            max_legal = max([t for t in tops if g[j][0] % 2 != t % 2])
            # The same tile is never moved twice in a row, and the floor isn't movable.
            if g[j][0] != moved and g[j][0] > 0:
                # Count the number of empty spaces.
                num_zeros = len([z for z in tops if z == 0])
                # Tiles are only placed on either larger tiles or in empty places.
                if g[j][0] < max_legal or num_zeros > 0:
                    movable = True
            if not movable:
                j += 1
        
        moved = g[j][0]
        
        ## Second, find a place to move the movable tile to. ##
        legal = False
        # Iterate from the other end of the board.
        k = 2
        while not legal:
            # A spot is legal if the tile there has different parity and is larger than
            # the tile being moved, or it is empty.
            if (tops[k] % 2 != g[j][0] % 2 and g[j][0] < tops[k]) or tops[k] == 0:
                legal = True
            if not legal:
                k -= 1
        
        # Perform the move
        g[k] = [g[j][0]] + g[k]
        g[j] = g[j][1::]

        print g

        S = [sum(s) for s in g]
        X += [S[0]]
        Y += [S[1]]
        Z += [S[2]]
    
    return (X,Y,Z)

n = 10
game = [range(1,n+1)+[0], [0], [0]]

X, Y, Z = solve(game,n)

fig = p.figure()
ax = p3.Axes3D(fig)
ax.plot3D(X,Y,Z)
ax.view_init(30, 45)
fig.add_axes(ax)
p.show()