The Tower of Hanoi 

Kevin McMillin | Arizona State University | Tempe, Arizona 
MAT 267: Calculus III for Engineers | Spring 2008 
Supervised by Professor Naala Brewer
Maple 11 Version - Tower of Hanoi

Introduction 

The Tower of Hanoi is a puzzle game invented by the French mathematician Édouard Lucas in 1883.  According to a legend that Lucas may have either heard secondhand or invented himself, there was once an Indian temple where a mathematical puzzle was used to discipline young priests.  The legend says that, since the beginning of time, 64 gold disks have surrounded three time-tested columns in a large room inside the temple. The priests have been working for centuries to move the disks, each one on top of a larger one, from the left column to the right column.  Upon completion of the puzzle, the legend claims the world will end.  In some variations of the story, the priests are only allowed to move one disk per day, while other versions claim the priests may make unlimited moves until they have solved the puzzle.  However, they are restricted in all versions by three simple rules: 

 

• Only one disk may be moved at a time.

 

• Each move involves taking the upper disk from one of the pegs and placing it on another peg.

 

• No disk may be placed on top of a smaller disk.

 

 

Most versions of the game today (marketed as toys for children) have eight or fewer disks rather than 64.  This is still a complicated puzzle even with only eight disks—it may even seem impossible to beginners.  In order to develop a method to solve this puzzle, it will help to start simply.  Let's consider the same puzzle with three disks. The images below show the most efficient solution, with the moved disk shown in dark blue. 

 

 

 

 

 

 

By examining the seven steps needed to solve a three-disk puzzle closely, we arrive at an interesting solution.  The quickest process for solving the puzzle involves three methods which work for any value of disks (that is, the process of solving a two disk puzzle is the same as it is for 64 disks): 

 

• Move the topmost disks from the leftmost peg to another peg using a temporary peg as storage; in the above example, we moved the topmost two pegs from peg A to peg B using peg C as storage.

 

• Move the largest disk from the leftmost peg to the rightmost peg directly; in the above example, we moved the largest peg from peg A to peg C.

 

• Move the topmost disks from the storage peg to the rightmost peg using another storage peg; in our case the storage peg was A.

 

 

What has developed is called a recursive algorithm.  A recursive algorithm is a method of defining a process by using the process within the definition.  It is frequently seen in both mathematics and computer science.  Perhaps the most famous recursive is the Fibonacci sequence, where . 

 

Solving the Tower of Hanoi efficiently with three, four, or even five disks can be a fun challenge; however, as more and more disks are added, the number of steps increases exponentially.  To see this relation, we shall let represent the number of moves we must make to solve the puzzle.  The first and last steps, therefore, take moves, while the intermediate step takes one move.  Thus, the entire puzzle of disks will take moves. To help us put this concept into a recursive pattern, we will consider empirical evidence.  A two-disk puzzle takes three moves; a three-disk puzzle will take seven moves.  A four-disk puzzle will take fifteen moves, and a five-disk puzzle will take 31 moves.  By inspection, we can see that the number of moves can be represented as . 

 

Incidentally, a 64-disk Tower of Hanoi puzzle would take moves to solve.  At a rate of one per second for all time, how long will this take? 

 

>

2^64-1;

 

(1.1)

 

>	evalf[3]((2^64-1)/(365*24*60*60));

 

(1.2)

 

 

Even at lightning-fast speed, the priests will be working for almost 600 billion years!  Needless to say, the world should be safe for at least a little while longer. 

 

To help us find a solution for solving puzzle with several disks, let's develop a Maple procedure to automate the solution and output an animated image. 

The MoveSequence Procedure 

 

First let us define the actual procedure of moving the disks.  Before we can begin animating, we must know which pegs to move and where to move them.  Using the three-step method described above, we define our sub-procedure MoveSequence.  A, B, and C represent each of the three pegs respectively. 

 

>

MoveSequence := proc( n, A, B, C )   #if number of disks = 1, then print [A,C] if n=1 then [A,C] #else call the MoveSequence procedure recursively once to move the topmost N-1 pegs to the storage peg, #then move A to C, then call the MoveSequence procedure again to move the topmost N-1 pegs from the storage #peg to the destination peg else op([MoveSequence(n-1,A,C,B),[A,C],MoveSequence(n-1,B,A,C)]); fi end;

 

(2.1)

 

 

When this MoveSequence runs it will generate a list of pairs .  For practical purposes, let X represent the peg of origin and Y represent the peg of destination.  So means "Move the topmost disk from peg X to peg Y."  Let's try running this procedure with three disks and observe the output. 

 

>	MoveSequence(3,A,B,C);

 

(2.2)

 

 

Each time the MoveSequence runs, it uses recursion for its first and last steps, running the process again and again for disks until it reaches the base case—that is, where .  Consider what happens if we have only one or two disks: 

 

>	MoveSequence(1,A,B,C);

 

(2.3)

 

>	MoveSequence(2,A,B,C);

 

(2.4)

 

 

We see that with 1 disk only the intermediate move is required, and with two disks only one call of each of the first and last methods is needed. 

Creating an Animation Base 

Now that Maple knows which disks it needs to move and where to move them, we can begin to draw the board on which our pegs will rest.  We'll do this with a simple 2D plot filled with various rectangles. 

 

>

#get plottools and plots packages with(plottools): with(plots): #create the PegSetup using a sequence of rectangles, with heights and widths arbitrarily based to fit inside a small Cartesian coordinate system PegSetup:= seq(plottools[rectangle]( [i,0] , [i+.1,4] , color="Gold" ), i=1..3), plottools[rectangle]( [0,-.5] , [4,0] , color="DarkGrey" ): plots[display](PegSetup, axes=none, view=[0..4, -1..4], title = "Tower of Hanoi", titlefont=[Arial, Roman, 18]);

 

 

Letting Maple Store and Move the Disks 

 

Now that we have a board, we need to write another procedure which will be able to move disks from one peg to another.  To do this, we'll first need to number the disks 1, 2, 3, and so on to n.  We start by placing all the disks in our puzzle (we'll use seven disks this time) on the first peg—we'll use three lists to store them.  Here's what our lists would look like for a seven-disk puzzle: 

 

>	n:=7:[seq(n+1-i,i=1..n)],[],[];

 

(4.1)

 

 

So on our first peg we have disks 1 to 7, and our second and third pegs are empty.  But each peg has to store more than just a number, and it needs to be easily accessible by name.  Each location also needs to store the height and letter of the peg in order for our animation and move sequence to work correctly.  So we use a table of three indices, A, B, and C, created with a table initializer each storing the beginning location and number of disks: 

 

>	L:=table([(A)=[seq(n+1-i,i=1..n)],(B)=[],C=[]]);

 

(4.2)

 

 

No matter how many disks there are, the first move in our procedure will always move peg A's topmost disk to peg C.  In order to accomplish this, we'll need to create another procedure called MoveOneDisk.  MoveOneDisk will take a table and a list as arguments, and it will parse the list to grab the topmost disk of A and move it to C. 

 

>

MoveOneDisk:=proc(P::table,M::list) #we'll need some local variables to store temporary lists and tables local a, b, c, n, p; #create a temporary table p identical to table P by calling the entries for each index p:=table( [(A)=L[A] , (B)=L[B] , (C)=L[C]] ); #call the move generated above--[A,C] and store its values in two local variables a:=M[1]; b:=M[2]; #extract the number of operands (disks) in L[a]--7 in our example---and store it as n n:=nops( L[a] ); #set p[b] (an index of the table p) equal to the operand of P[b] at the nth value of P[a] p[b]:=[ op(L[b]) , L[a][n] ]; #set p[a] equal to P[a] at each value from 1 to n-1 (that is, remove the nth value of p[a]) p[a]:=L[a][1..n-1]; #finally, return the table p p; end;

 

(4.3)

 

 

After defining the procedure for moving a disk, let's determine our MoveSequence for a tower of seven disks. 

>	MoveSequence(7,A,B,C);

 

(4.4)

 

 

That's 127 moves!  Let's try the first two draws in the sequence using our new procedure. 

 

>	L:=MoveOneDisk(L,[A,C]): print(L);

 

(4.5)

 

 

As we can see, the nth (7th in this case) entry of the list L[A] has moved to L[C].  Let's try moving a disk from A to B now.
 

>	L:=MoveOneDisk(L,[A,B]): print(L);

 

(4.6)

 

 

To apply the MoveOneDisk procedure to our animation and have it seen, we'll need to create another procedure which draws our move. 

 

The MoveOneDiskDraw Procedure 

In order to create our animation, we'll need to let our table L store the sequence of moves created by the MoveSequence procedure we wrote above.  Each move will be applied to the MoveOneDisk procedure and this procedure will set out to create an image of the move.  When all the images are concatenated along with the PegSetup we created above, we'll have our animation.
 

>

MoveOneDiskDraw:=proc(T::table,q,r,n) #the inputs q and r are arbitrary values representing the "height" and "width" of the pegs--that is, the space #on the Cartesian plane in which the pegs are drawn and separated.  We will use 5 and 1, respectively, for our example. #we'll need four more local variables for this procedure: w to store the width #of the smallest drawn disk, h for the height (always 1/2) of each disk, #t for a table to store the peg reference numbers, and l for an traversal tool through the passed table parameter local h,w,t,l; #get packages for plots and plottools with(plots): with(plottools): #assign the width of the disk to be the 1/2 over the number of the disk #larger disks will therefore be the ones with the larger disk numbers and larger disk widths w:=1/(3*n); #the height will remain 1/4 h:=1/4; #use t to set up a local table for the pegs t:=table([(A)=1,(B)=2,(C)=3]); display(seq(seq(rectangle([t[l]-T[l][j]*w,j*h],[t[l]+T[l][j]*w+.1,(j-1)*h],color="Maroon"),j=1..nops(T[l])),l=[A,B,C]),axes=none); end: r:=MoveOneDiskDraw(L,5,1,6): display(r,PegSetup, title="Tower of Hanoi", titlefont=[Arial,Roman,18]);

 

 

So now we have a procedure which can draw the output of our table.  However, this is only one of 127 draws for a tower of seven disks.  To create the animation, we'll need to create our final procedure, TowerOfHanoi.  This procedure will call all of the previously demonstrated procedures and output a Maple animation showing each step of the most efficient solution when it completes. 

The TowerOfHanoi Procedure 

>

TowerOfHanoi:=proc(n::{1,2,3,4,5,6,7,8,9,10,11,12}) #in consideration for Maple's solving power, we'll limit the number of disks to 12. #use local procedures local MoveSequence, MoveOneDisk, MoveOneDiskDraw, DrawGeneration, i, L, Q, PEG_HEIGHT, PEG_WIDTH; PEG_HEIGHT = 5; PEG_WIDTH = 1; #import necessary packages with(plottools): with(plots): #copy above procedures, separated by comment lines #-------------------MoveSequence------------------- MoveSequence := proc( n, A, B, C ) if n=1 then [A,C] else op([MoveSequence(n-1,A,C,B),[A,C],MoveSequence(n-1,B,A,C)]); fi end; #-------------------MoveOneDisk-------------------- MoveOneDisk:=proc(P::table,M::list) local a, b, c, n, p; p:=table( [(A)=L[A] , (B)=L[B] , (C)=L[C]] ); a:=M[1]; b:=M[2]; n:=nops( L[a] ); p[b]:=[ op(L[b]) , L[a][n] ]; p[a]:=L[a][1..n-1]; p; end; #-----------------MoveOneDiskDraw------------------ MoveOneDiskDraw:=proc(T::table,PEG_HEIGHT,PEG_WIDTH,n) local h,w,t,l,PegSetup; PegSetup:=seq(rectangle( [i,0] , [i+.1,4] , color="Gold" ), i=1..3), plottools[rectangle]( [0,-.5] , [4,0] , color="DarkGrey" ): plots[display](PegSetup, axes=none, view=[0..4, -1..4]); w:=1/(3*n); h:=1/4; t:=table([(A)=1,(B)=2,(C)=3]); display(seq(seq(rectangle([t[l]-T[l][j]*w,j*h],[t[l]+T[l][j]*w+.1,(j-1)*h],color="Maroon"),j=1..nops(T[l])),l=[A,B,C]),axes=none,PegSetup); end: #----------------DrawGeneration-------------------- #This takes the sequence of draws and stores them as a list, DrawGeneration. DrawGeneration:=[MoveSequence(n,A,B,C)]; #create the initial table with all disks on peg A L:=table([(A)=[seq(n+1-k,k=1..n)],(B)=[],C=[]]); #create a new image plot for each move Q:=MoveOneDiskDraw(L,PEG_HEIGHT,PEG_WIDTH,n); for i from 1 to nops(DrawGeneration) do #this creates the move L:=MoveOneDisk(L,DrawGeneration[i]); #this step plots it Q:=Q,MoveOneDiskDraw(L,PEG_HEIGHT,PEG_WIDTH,n);  od; display(Q, insequence=true, title="Tower of Hanoi", titlefont=[Arial,Roman,18]); end:

 

Finally, we run the solution and watch the animation! 

The Full Solver Animation 

 

>	TowerOfHanoi(7); #the procedure takes inputs from 1 ≤ n ≤ 12 #to play the animation, click anywhere on the plot and use the submenu

 

 

>

 

While it may not prove very fruitful in solving a 64-disk puzzle, hopefully our animation should aid solvers young and old alike should they get stuck solving the Tower of Hanoi puzzle. 

References 

I must thank the following authors for their works which greatly helped me complete this project. 

 

• Anatole, Beck, Michael W. Bleicher, and Donald S. Crowe. Excursions Into Mathematics. New York: Worth Publishers, 1969.

 

• Rosen, Kenneth H. Discrete Mathematics and Its Applications. Boston: WCB/McGraw-Hill, 1999.

 

• Kraft, Roger. "Maple Programming: Complete Set of Lessons." Maplesoft Application Center. Oct. 2003. <http://maplesoft.com/applications/app_center_view.aspx?AID=1570>.

 

• Lewis, John, Peter J. DePasquale, and Joseph Chase. Java Foundations. Boston: Pearson/Addison-Wesley, 2008.