AI ClassFinal Exam - Question 1The 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. 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: Mn=2Mn-1+1. Perhaps it is better to write a program that can actually solve the game. This logic can be very easily programmed using what is called a recursive function. 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. # 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. ![]()
|