Towers of Hanoi

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. We receive a few cents from each purchase.   Thanks.


Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

 

Problem Description

In a monastery in Benares India there are three diamond towers holding 64 disks made of gold. The disks are each of a different size and have holes in the middle so that they slide over the towers and sit in a stack. When they started, 1500 years ago, all 64 disks were all on the first tower arranged with the largest on the bottom and the smallest on the top. The monks' job is to move all of the disks to the third tower following these three rules:

1. Each disk sits over a tower except when it is being moved. 
2. No disk may ever rest on a smaller disk.
3. Only one disk at a time may be moved.

The monks are very good at this after all this time and can move about 1 disk per second.  When they complete their task, THE WORLD WILL END! The question is, how much time  do we have left? 

Techniques & Background

This is version 1 of the Towers problem.  It knows what to do, but doesn't really do it.  

Coming are Version 2, makes the moves internally and displays a list of which disks move to which pegs and  Version 3 which adds graphics so you can drag the disks around or watch the program move them. 

But first to solve the basic problem.  Here is a good example of the method of mathematical proof known as "Mathematical Induction".  The Induction method applied to our problem says that if you can solve it for one disk and if, assuming you can solve the problem for M disks, you can tell how to solve it for M+1 disks, then you can solve the problem for any number of disks!  

So, we can surely solve the problem for one disk - just move it.  Given a stack of M+1 disks, and knowing how to move M disks, can we figure out how to solve the problem?  First notice that the top M disks of this pile wouldn't know about the bottom disk at all - since it's the largest disk, if it were alone on the tower, any other disk could move on top of it just like it wasn't there.  I'm going to use the word "pegs" for "towers" from now on - shorter.  Lets call the pegs A, B, and C and assume that we have  the M+1 disks on peg A.  We're assuming by induction that we can move the top M disks to another peg, say to B.  Presto, we did it!  So we now we have peg A left with the largest disk, peg B with the other M  disks and peg C empty.  Now move the largest disk from A to C.  Next,  since we have a method that moves M pegs from peg A  to peg B, we can just re-label the pegs appropriately  (so A has the M pegs, B is the one with the large disk on it that we want to move the other M to, and C is the spare).  Now apply our method for moving M pegs from A to B once again and we're done!

If you look at the source code, you'll see that that is exactly what the program does.   There is a procedure called MoveOne(A,B) that moves the top disk from peg A to peg B.  In this version it doesn't do much except add 1 to a counter and call Application.Processmessages to give Windows a chance to do handle other messages (like the user hitting the stop button).  Later on, Moveone will list the move or do the graphics stuff.

The other major procedure is called MoveStack(n,A,B,C).  Its job is to move a stack of n disks from A to B using peg C as the spare.  It does this using another bit of magic called recursion.  Recursion occurs when a procedure calls itself.  See this article in Delphi Techniques  for a more extensive discussion.  To move along here, MoveStack performs the 3 steps we described above 

Procedure MoveStack(n,A,C,B:Integer);

Begin

   If n=1 

   then MoveOne(A,C); {If there's only one to move, move it} 
   else 
   Begin
       {Move n-1 disks from peg A to peg B using C as the spare}

       MoveStack(n-1,A,B,C);
       MoveOne(A,C); {Move 1 disk to Peg C}
       {Then move n-1 disks from B  to  C using A as the spare}

       MoveStack(n-1,B,C,A);
   end;

end;

That's it.  Some code to display output and to let the user stop if he puts in a big number and estimate time to complete and we're done.  For now.

 Running/Exploring the Program 

Suggestions for Further Explorations

Next time, we'll present a version smart enough to list the moves.  Work on that if you're bored and looking for something to do.

Two more problems in recursion. 

See this article on Recursion describing a couple of examples of recursive function calls.

Then:

  • Write a program to take a positive integer N and display N! (N factorial) when the user presses a button.

  • Write a program to display the first 50 Fibonacci numbers.  

  

  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2017, Gary Darby    All rights reserved.