Solved
Experts Challenge I: Towers of Hanoi
Posted on 2004-04-26
C# Experts Challenge
After working on some questions with AvonWyss and others, I had the idea of creating an “Experts’ Challenge.” I have come up with a challenge for this week and we will see what kind of interest there is out there. Any Experts-Exchange members are welcome to participate, so don’t be intimidated by the title!
Experts Challenge I: Towers of Hanoi
“It is rumored that somewhere in Asia a group of spiritually advanced monks is hard at work transferring golden disks. When they are finished moving a tower of 64 of these disks from the first peg to the third peg of a sacred three-peg stand, then the next Maha Pralaya will begin, in which the universe will dissolve and revert to its unmanifested state. The 64 disks have different sizes, and the monks must obey two rules: (1) only one disk can be moved at a time, and (2) a bigger disk can never be placed on top of a smaller disk.”
This is the infamous “Towers of Hanoi” problem. This problem can be found in many programming textbooks in a section labeled (you guessed it) “Recursive Algorithms.”
The challenge this week is to create a method that solves the Towers of Hanoi problem *non-recursively*.
Rules:
1. The problem must be solved in one method, and this method cannot call itself (directly or indirectly – no tricks!).
2. The pegs must be identified by the integers 0, 1, and 2 for the first, second and third pegs (i.e.: 0 based index).
3. The method must have the same prototype as below: string (int n, int start, int finish), where n is the number of disks to move, start is a peg from the set {0, 1, 2} finish is a remaining peg where you would like the tower to end up. So to move 8 disks from the first peg to the third peg, you would call “MoveTowers(8, 0, 2)”.
4. The method must return a string in the format “(x,y)” for each move of a disk where x is the starting peg, and y is the destination peg of a disk. For example, moving a disk from the first peg to the third peg would produce the string “(0, 2)”. Moving a tower of 2 disks from the first peg to the third peg would produce the string “(0,1)(0,2)(1,2)”.
5. You do not need to worry about argument checking. Assume that n will always be greater than zero, and start and finish will be two distinct elements from the set {0, 1, 2}.
######
Here is an example in c# of a recursive method that solves the Towers of Hanoi problem:
string MoveTowers(int n, int start, int finish)
{
if(n==1)
return String.Format("({0},{1})", start, finish);
else
{
int spare = 3 - start - finish;
return MoveTowers(n - 1, start, spare) + MoveTowers(1, start, finish) + MoveTowers(n - 1, spare, finish);
}
}
The method call “MoveTowers(3, 0, 1)” returns the string, “(0,2)(0,1)(2,1)(0,2)(1,0)(1,2)(0,2)”.
######
Good Luck!