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.

Mensa® Daily Puzzlers

For over 15 years Mensa Page-A-Day calendars have provided several puzzles a year for my programming pleasure.  Coding "solvers" is most fun, but many programs also allow user solving, convenient for "fill in the blanks" type.  Below are Amazon  links to the two most recent years.

Mensa® 365 Puzzlers  Calendar 2017

Mensa® 365 Puzzlers Calendar 2018

(Hint: If you can wait, current year calendars are usually on sale in January.)

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 

bulletBrowse source extract
bulletDownload  source
bulletDownload  executable

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:

bullet

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

bullet

Write a program to display the first 50 Fibonacci numbers.  

  

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