AI Class

Final Exam - Question 1

The Towers of Hanoi

To see the graphics below, you need to have Java enabled in your browser.

This has been the first question on the final exam of the course and was about the puzzle named Towers of Hanoi.
To goal of the game is to move a series of rings from the first peg to the last peg. Only one ring can be moved at once and it cannot be put on a ring of smaller size.
There were actually three answers to give: how many states has this game, what is the minimum number of moves to solve it and whether an heuristic based on the number of rings on the first peg was admissible or not.
The number of states can be computed thinking that each of the 4 rings can be on one of 3 different pegs. So each ring has 3 choices and since we have 4 rings in total, the number of states is 3 x 3 x 3 x 3 = 3⁴ = 81.
The heuristics is crearly admissible because to be valid it must never overestimate the real cost that is left. The cost in this case is obviously the number of moves left and, since you need at least one move to displace a ring out from the first peg, the heuristics is admissible, although is clearly a bad choice to solve this game.

The minimum number of moves necessary to solve this game is 15. To understand why, think about the following: to move 1 ring we need 1 move, of course. To move 2 rings we need to displace the preceding ring two times, so 2 moves, plus 1 move for the new ring. In general to move n rings, we need 2 times the moves for (rings-1) + 1, or in formula: M_n=2M_n-1+1.
Expanding this formula we arrive at the following one: M_n=Σ_{i=0 to n-1}2ⁱ,
which is also equivalent to: M_n=2ⁿ-1. Thus for 4 rings the answer is 15.
As you can easily understand, this number increases rapidly with the number of rings. For example solving a 64-rings game requires exactly 18,446,744,073,709,551,615 moves! If someone propose you to do that, please refuse, or, at 1 move per second, you will be busy for about 38 times the age of the universe :-)

Perhaps it is better to write a program that can actually solve the game.
To know how to solve it, let's think how we could solve a game with a single ring. I will call here the pegs a, b and c and the generic function will be move().
So for the single ring game, the solution is trivial: move(a,c).
Now let's think at a 2 rings game. We cannot move them at once, so the best strategy is to displace the top ring to the spare peg, then the base to the third peg, then move back the top ring on it. That is: move(a,b), move(a,c), move(b,c).
Now the intersting part: what about a 3 rings game? If we could move more than one ring at a time, except the bottom one, we could move the top sub-tower to the spare peg, then the base to the goal, then again the sub-tower from the spare to the goal.
But we already know how to move a 2 rings tower! So a 3 rings game can be solved applying the rules we found about moving 2 rings and now that we know how to move 3 rings, we will know how to move 4, and 5 ... thus any number of rings.

This logic can be very easily programmed using what is called a recursive function.
The recursive function will move a single ring to the destination, or will call itself to move a sub-tower. We could describe it with the following pseudo-code:

function hanoi(origin, destination, num_of_rings)
   if num_of_rings is 1, then move 1 ring from origin to destination
   otherwise
      call myself to move the top subtower to spare peg: hanoi(origin, spare_peg, num_of_rings-1)
      move 1 ring from origin to destination
      call myself to move the top subtower from spare peg to destination: hanoi(spare_peg, destination, num_of_rings-1)

I will illustrate now a real program, written in the Python programming language. If you have a Linux distribution, Python is most probably already installed in your system, or you can install it from the distribution repositories.
If you use Windows or Mac OS X, you can download the Python interpreter from: www.python.org.

# Python program to solve the Hanoi Towers with 4 rings
# written by Vinicio Coletti, Italy

# We define the 3 pegs as lists and the rings as numbers from 1 (smallest) to 4 (largest)
# the order is bottom to top. So the 'pegs' variable is a list of lists.
pegs=[['4','3','2','1'],[],[]]

# the move number
nmove=0

# a function that move a ring and print the game state
def move(a,b):
    global nmove
    pegs[b].append(pegs[a].pop())
    nmove+=1
    print "Move #%d"%(nmove)    
    for r in range(3,-1,-1):
        s='  '
        for p in pegs:
            if r<len(p): s+=p[r]+'  '
            else: s+='   '
        print s
    print       

# now let's define the main function, that will move
# from peg 'orig' to peg 'dest', 'num' number of rings
def hanoi(orig,dest,num):
    # if rings to move are 1, move directly and show state
    if num==1: move(orig,dest)
    # otherwise move sub-towers
    else:
        # since the sum of peg numbers 0,1,2 is 3, we compute which is the spare peg
        spare=3-orig-dest
        # let's move the top sub-tower on the spare peg
        hanoi(orig,spare,num-1)
        # now we move the bottom ring to the destination
        move(orig,dest)
        # and finally we move back the top sub-tower from the spare to the destination
        hanoi(spare,dest,num-1)

# now we need only the main program, which is very simple...
# we move from peg 0 to peg 2, 4 rings in total
hanoi(0,2,4)

Final note: the Towers of Hanoi is a classical example for recursive functions. I wrote my first program for it around 1985, using a Pascal compiler for the Commodore 64. Later on, I rewrote it in Borland Turbo Pascal on a 386 PC, then I felt no need of this puzzle :-) until I attended the online AI Class...

Here below you can see the original question, with my three correct answers.