Towers of Hanoi help

[Franco527]

Hello everyone,

I am trying to write program that solves the Towers of Hanoi game using recursion. I am suppose to get the input from the user about how many discs, the start peg, and end peg.

The way I am trying to solve it now is by hard coding the values (3 discs, start from peg#1 and end on peg#3).

The problem I am having is outputting what peg to move it too. Can someone point me in the right direction?

Main function:

int main(int argc, char *argv[])
{
         int start = 1;
	 int numDisk = 3;
	 int end = 3;
	 
	 towersHanoi(numDisk, start, end);

	return 0;
}

void towersHanoi(int disks, int start, int end)
{	
	if(disks>0)
	{
		towersHanoi(disks-1, start, end);
		cout << "Move disk from " << start << " to " << end << endl;
		towersHanoi(disks-1, start, end);
	}
}

The output

[csc103]$ ./towers 
Move disk from 1 to 3
Move disk from 1 to 3
Move disk from 1 to 3
Move disk from 1 to 3
Move disk from 1 to 3
Move disk from 1 to 3
Move disk from 1 to 3

Thank you for the help

[nuzzle]

The problem I am having is outputting what peg to move it too. Can someone point me in the right direction?

I've never had any problems with recursive formulations but I've always found this particular problem especially difficult so I can't help you with a deeper understanding. Still the net is full of solutions you can use. I think you need to include a middle peg and the stop criterion seems wrong. Try this,

void TOH(int n, int p1, int p2, int p3) {
	if (n>1) TOH(n-1, p1, p3, p2);
	printf("Move top disc from %d to %d.\n", p1, p2);
	if (n>1) TOH(n-1, p3, p2, p1);
}

[2kaud]

void moveDisks(int count, int needle1, int needle3, int needle2)
{
   if (count > 0) {
      moveDisks(count - 1, needle1, needle2, needle3);
      cout << "Move disk " << count << " from " << needle1 << " to " << needle3 << endl;
      moveDisks(count - 1, needle2, needle3, needle1);
   }
}

The analysis is this
1) Move the top n - 1 disks from needle1 to needle2 using needle3 as intermediate
2) Move disk number n from needle1 to needle3
3) Move the top n-1 disks from needle2 to needle3 using needle1 as intermediate

[2kaud]

The analysis of Towers of Hanoi is quite interesting.

Background
At the creation of the universe, priests in the temple of Brahma were supposedly given three diamond needles, with one needle containing 64 golden disks. Each golden disk is slightly smaller than the disk below it. The priests' task is to move all 64 disks from the first needle to the third needle. The priests were told that once they had moved all of the disks from the first needle to the third needle by only following the rules, the universe would end. The rules given were:
1) Only one disk can be moved at a time
2) The removed disk must be placed on one of the other needles
3) A larger disk cannot be placed on top of a smaller one

If needle 1 initially contains the 64 disks then the number of moves required to move all 64 disks from needle 1 to needle 3 is 2^64 - 1 (2 power 64 - 1). or approx 1.6 * 10^19.

The number of seconds in one year is approx 3.2 * 10^7 1.6 * 10^19 = 5 * 3.2 * 10^18 = 5 * (3.2 * 10^7) * 10 ^11
= (3.2 * 10^7) * (5 * 10^11)

If the priests move one disk per second and they never rest then the time taken to move all 64 disks from needle 1 to needle 3 is roughly 5 * 10^11 years. It is estimated that our universe is about 15 billion years old (1.5 * 10^10)

5 * 10^11 = 50 * 10^10 which approximates to 33 * (1.5 * 10^10) thus showing that our universe will last about 33 times as long as it already has!

If a computer can generate 1 billion (10^9) moves per second, then the number of moves that the computer could generate in one year is (3.2 * 10^7) * 10^9 = 3.2 * 10^16

So the computer time required to generate the 2^64 moves is
2^64 approxs 1.6 * 10^19 = 1.6 * 10^16 * 10^3 = (3.2 * 10^16) * 500

Thus it would take about 500 years for the computer to generate the 2^64 moves at the rate of 1 billion moves per second.

[Franco527]

Thanks for the help. I was able to fix it and get the right answer with this code:

void towersHanoi(int disks, int start, int middle, int end)
{
	if(disks>0)
	{
		towersHanoi(disks-1, start, end, middle);
		cout << "Move disk from " << start << " to " << end << endl;
		towersHanoi(disks-1, middle, start, end);
	}
}

I am having trouble tracing the recursion by hand. The double recursive calls is throwing me off. The way I trace it is by doing the first recursive calls and printing out the moves, then doing the second recursive calls and then printing those moves. Is that the correct way?

[nuzzle]

Is that the correct way?

Personally I've given up on the recursive solution to this problem but try this video from MIT, it may work for you,

http://video.mit.edu/watch/blossoms-...hinking-10237/

The call pattern is pretty simple actually. It's a so called inorder traversal of a binary tree. The same you get for example when flattening a math expression tree using parentheses, like say

(a + b) * (c + d)

You read from left to right. First you encounter a left child (a), then the parent (+), and then a right child (b), etcetera.

The problem for me is the intricate swapping pattern of the parameters in the recursive function calls. What says it won't get stuck in a dead end or cycle or something? After all it's a constrained setting and there may not even exist a way out.

The recursive solution doesn't click with me at all. Sure it works but the recursive formulation itself doesn't explain why. It leads to an ad-hoc solution that accidentally happens to work. It's not a good example of problem solving using recursion. It just leaves everybody feeling stupid, including your desperately hand-waving professor.

[2kaud]

The Towers of Hanoi is one of those problems that all computer science students have to 'experience' - as it helps with 'problem solving'!!?? I got it in a written pascal paper as part of my computer science degree more years ago than I care to remember. It's like the cannibals one and others - mug it up, recite it, tick the box and move on.

[OReubens]

The principle is easy enough. You just have to figure out the basic idea then working out the recursive function is easy.

Basically
to move the tower from A to B:
you first need to move the tower minus the bottom disk to the spare peg. only then can you move the bottom diskfrom A to B. after this move the tower minus the bottom disk onto the bottom disk

and this is the basis of the recursive function, to move the tower minus the bottom diskis the same problem just one less disk.


that also explains the working of the recursive function and the 2 calls.
the 2 calls are for moving the tower minus one on the spare peg, move the bottom and move the tower again.


This also means that if you do this by hand and have no computer
if you have an odd number of disks, then your first move is moving the smallest disk on the spare peg. if you have an even number of disks you move it to the target peg.