# towers of hanoi. recursion, i'm sure this will be on someone'sproblem set

Discussion in 'C Programming' started by G G, Sep 9, 2013.

1. ### G GGuest

uh?

i can solve it by hand, the towers of hanoi.
but, i'm missing the recursion algorithm altogether.
wait, don't give me the answer, maybe a hint...
the base cases is what? and how did you think through it
to get the base case. (you don't have to give me the base case,
but maybe what,how, maybe what was right, what should
i be looking for or thinking about to find the base case. it can't
be the "number of disk" to be moved are on target pole?
it would also be the case that the other poles are empty.

and, in the logic of the program don't i have to check on
the size of the disk if one is on the peg before i can move
a disk to a pole?

let me also add. the function is suppose to have four parameters
a) The number of disks to be moved
b) The peg on which these disks are initially threaded
c) The peg to which this stack of disks is to be moved
d) The peg to be used as a temporary holding area

not given, i created solveTower prototype:

solveTower( int numberOfDisk, int initialPegWithDisk, int finalPegWithDisk,
int temporaryHoldingPeg);

and, so, this is to be called on until the base case occurs?

should i post the exercise's text? as you can see i'm confused a bit.
a great bit.

g.

G G, Sep 9, 2013

2. ### Eric SosmanGuest

For me, the crucial step in inventing a recursion is not
identifying the base case, but finding how to decompose the
large problem into smaller problems. In this case, you look
at the original stack of disks 1,2,...,N on peg A, and you
think "If only I could move the upper disks 1,2,...,(N-1) from
A to B, then I could move disk N from A to C, then I could move
1,2,...,(N-1) from B to C." And there's your decomposition:
You began with the problem of moving N disks, and now you've
got two smaller problems (moving N-1 disks, twice) plus one
move of the lone disk N that you know how to do directly.

This should give you enough to get well started.

Eric Sosman, Sep 9, 2013

3. ### G GGuest

ok, i've got it. i think.

thanks. decomposition flip the switch.
right, as you say n-1 twice and a move... smaller and smaller problem to solve
right, right.
(n-1, A, B, C)
move( n, A,C)
(n-1, B, C, A)

something like that... ok. let me think on it and code it up, but yeah, good,
good. great hint!

thanks a lot,

g.

G G, Sep 9, 2013
4. ### Bill DavyGuest

You can make it more interesting with a random initial allocation of disks,
in which case you find the first disk on C which is out of place (the bad
disk), move everything above the bad disk off it (to A or B - the choice
matters), move the bad disk (to B or A) and then move the correct disk to C.
But that may not be optimal either.

Bill Davy, Sep 10, 2013
5. ### G GGuest

This should give you enough to get well started.
Bill, first things first.

Guys and Ladies let me apologize about how long my writing will be.
I just think there is something really cool about this and I don't want
to miss it.

Ben gave me great insight into thinking about the problem, but
I'm having trouble tracing my thoughts by hand. pencil and paper.
I think I'm on the right track, but apparently I don't fully understand.
So, if you all don't mind, please a little more discussion???

Given:
Disks
Three Pegs (or poles) (for this problem)
restrictions: smaller disk must always be on top of a larger disk
only one disk can be moved at a time to a peg/pole.

function parameters:
The number of disks to be moved
The peg on which those disks are initially threaded
The peg to which this stack of disks is to be moved
The peg to be used as a temporary holding area.

Ben discussion of decomposing the problem to a smaller
and smaller problem. simpler and simpler

Find: a recursive algorithm that solves the Tower of Hanoi.

Solution:

Let the poles have the names A, B, and C. ( I found that I had to make
the names a little more generic as I try to trace the function by hand)

The disks will start on A and all will have to be moved to C, with the constraints
mentioned above.

In the simplest of cases, there is only one disk. So that disk can be moved
to the final destination. A direct move. from A to C. so let me call A the
source of the disk and C the destination of the disk.
move from source to destination.

The next simplest of cases, there are two disk. So, one the smallest disk
which is on top of a larger disk must be move to a temporary locations,
amongst the three pegs.

So move a disk from A to B. From source to the temporary peg named B.

Now a direct move can take place. move a disk from A to C. I say direct only
because I am envisioning the pegs and disk as if I can reach out and grab and
move them. Of course, this is the larger of the two disk.
move a disk from A to C
move a disk from source to destination.
( here I realize the destination is changing, the destination will not always
be the same peg for each move.)

Finally move the disk on B to C. The peg B temporary held the smallest disk.
move a disk from source to destination. ( here again I note that source is not
A peg, source should be the peg from which I am grabbing the disk.
so, yes, move a disk from source to destination. that thought took a while
to grasp even with Ben's very very good hint. (different sources and different
destination. i mean i new that each disk may have to go to a different peg, but
using A,B,C, the concrete, instead of the generic source, destination, temporary
kept tying me up, mentally.

Ok, armed with the generic thought of, move a disk from a source to a destination
the next case, starting with three disk. This is where I seem to loose it.
With three disk I understand I'm going to need to temporary move a disk to
another peg. Also, I realize that must happen more than once. Meaning that there
are not pegs to place the smaller disk so that a direct move of the largest
disk can go to the final destination. ( OK, too many word, ok )

The concrete: A, B, C, three disk on A with smallest on top, largest at the bottom.

move a disk from A to C ( i know do this from trial and error otherwise i would
end doing more moves...)
move a disk from A to B

at this point, the largest disk is by itself on peg A, but it cannot be moved to
peg C because the smallest disk is there.
so, the smallest disk, which is on C, has to be moved to a temporary location
which meets the constraints, smaller on top of larger. Therefore the disk on C
can be moved to B.

Now the disk on A can be moved to C. This places the largest disk on C.

There are two disk on B so, there are actually two places where the smallest disk
may go and hold to the rules. The smallest could be moved to C or the smallest
could be moved to A. Moving the smallest to B, is not helping. so, I temporarily
place the smallest disk on A, or move a disk from B to A temporarily.

move a disk from B to C

move a disk from A to C

done.

P-code:

solveTowerOfHanoi ( int n, int source, int destination, int temporaryPeg)
{
if ( n == 1)
print the move "one disk from source to destination" // source: A,B,C
// destination: A,B,C
else
begin
solveTowerOfHanoi( n -1, source, temporaryPeg, destination)
/*
this is what i think is confusing me, the names, here i realize
i am passing into the function the destination, temporaryPeg
*/
move from source to destination (here destination is temporaryPeg)

/*
the following call's placement of parameters seem to take some
insight, right? i'm missing it.

*/
solveTowerOfHanoi( n - 1, ............ what.................)

end /* else */

I had this problem before and I thought I had mastered it. once the base case is occurs,
tracing the function back up, so to speak (write).
n=3
solveTowerOfHanoi ( 3 - 1, A, C, B )

solveTowerOfHanoi ( 2 - 1, A, B, C )

[--- solveTowerOfHanoi ( 1 -1, A, C, B )

here n = 1
print the move one disk from source to destination
so move one disk from A to C
[-----------

aren't i back at the: solveTowerOfHanoi ( 2 - 1, A, B, C )
so that means ???

move from source to destination
move from A to B

solveTowerOfHanoi ( 2 - 1, ...... what........ )

here's where i have confused myself. do i think about the second to last move or
the next move? at this point the source must change? the source needs to
be C and destination needs to be B... so

solveTowerOfHanoi ( 2- 1, C, B, A) which would lead to
solveTowerOfHanoi ( n-1, destination, temporaryPeg, source)

so:

P-code:

solveTowerOfHanoi ( int n, int source, int destination, int temporaryPeg)
{
if ( n == 1)
print the move "one disk from source to destination" // source: A,B,C
// destination: A,B,C
else
begin

solveTowerOfHanoi( n -1, source, temporaryPeg, destination )

move from source to destination (here destination is temporaryPeg)

solveTowerOfHanoi( n - 1, destination, temporaryPeg, source )

end /* else */

} /* solveTowerOfHanoi */

right? or close? i mean where did i lose it?

thanks, i know it's wordy .... sorry....

g.

G G, Sep 12, 2013
6. ### Eric SosmanGuest

Let me in turn apologize for the brevity of my reply.
Here's where you need to change viewpoints. Instead of "one disk
atop a larger disk," try to see "a pile of one or more disks atop a
larger disk."

Eric Sosman, Sep 12, 2013
7. ### G GGuest

solveTowerOfHanoi ( int n, int source, int destination, int temporaryPeg)
{
if ( n == 1)
print the move "one disk from source to destination" // source: A,B,C
// destination: A,B,C
else
begin

solveTowerOfHanoi( n -1, source, temporaryPeg, destination )

move from source to destination

solveTowerOfHanoi( n - 1, temporaryPeg, destination, source )

end /* else */

} /* solveTowerOfHanoi */

ok.

but to get that algorithm, i coded up the one i presented earlier.
i could see where the problem was from the executing program.
well, i got there, but i should have been able to do it with out the computer.
i need to revisit my logic in the last solveTowerOfHanoi(), as to why i missed it the
first time through. what is going where and why that's the case.

i guess my thinking was backwards... i thought of a pile of disc that i could not move, or i did
not know how to move, but i did know how to move one disc, so, i kept working up
the disc from n.

to me the n represents starting at the bottom of the disc and n-1 represents working
up the disc column until i got to the top one.

that maybe why the first algo was off...

thanks,

g.

G G, Sep 12, 2013
8. ### G GGuest

On Thursday, September 12, 2013 3:19:35 PM UTC-4, G G wrote:

Bill, i'm going to try the problem you proposed.

the solution may not be pretty.

g.

G G, Sep 12, 2013
9. ### BartCGuest

Did your solution work? I've had a go and it looks similar to yours. But the
way I did it:

I use recursion a lot but I found this puzzle difficult! So I had a go with
numbers on bits of card, moving them between 3 piles (I used to use playing
cards, but haven't got any). This way I discovered the general strategy.

The next step was coding something, but I avoid C; use an easier language
(eg. Python) to play with algorithms, only coding in C, if that is the
requirement, when it's all working! (That means you can also ask in any
programming forum, as algorithm is usually independent of language).

For this, I needed to find a representation for the pegs and discs, and I
also found it essential to be able to display the current state of the pegs.
For simplicity, shown horizontally, so the initial state might be shown as:

Peg 1: (10 9 8 7 6 5 4 3 2 1 )
Peg 2: ()
Peg 3: ()

And the final state (if it worked!) might be:

Peg 1: ()
Peg 2: (10 9 8 7 6 5 4 3 2 1 )
Peg 3: ()

The central function I had, the one similar to yours, looks like this
(consider this pseudo-code):

proc movediscs(n,a,b)=
if n=1 then
movedisc(a,b)
else
c:=thirdpeg(a,b)
movediscs(n-1,a,c)
movedisc(a,b)
movediscs(n-1,c,b)
endif
end

One difference is that this function works out the temporary peg for itself
(you need a function that, given two different values from 1 to 3, returns
the third value).

The function movedisc() moves a single disc (from the top of peg a to the
top of b), this is where the actual work is done, but this is irrelevant to
the algorithm.

BartC, Sep 13, 2013
10. ### Ben BacarisseGuest

Things get simpler if you allow for the possibility of moving no discs.
That's the way I like to do it, but it seems to be rare in all the
presentations I've seen.

<snip>

Ben Bacarisse, Sep 13, 2013
11. ### BartCGuest

Do you mean, not bothering to explicitly represent the state of the pegs and
discs?

I have some benchmark programs that do that, just go through the motions (as
the recursive efficiency was more important), for example:

void hanoi(int num_discs,int start,int end) { /* not my code... */
if (num_discs==1) return;
hanoi ((num_discs - 1), start, 6-start-end);
hanoi (1, start, end);
hanoi ((num_discs - 1), (6-start-end), end);
}

But I was interested in deriving this code, and also in actually moving
discs around so that at each step I could see what it was up to.

BartC, Sep 13, 2013
12. ### G GGuest

Yes, the final algorithm did work. The earlier one presented had an error in
the placement of the choices of source, destination, and temporary pegs to
be past into the last recursive call in the function. Below is the correct one.
Well, the one I used to produce the program.

---------------------------------------------------------------------
solveTowerOfHanoi ( int n, int source, int destination, int temporaryPeg)
{
if ( n == 1)
print the move "one disk from source to destination" // source: A,B,C
// destination: A,B,C
else
begin

solveTowerOfHanoi( n -1, source, temporaryPeg, destination )

move from source to destination

solveTowerOfHanoi( n - 1, temporaryPeg, destination, source )

end /* else */

} /* solveTowerOfHanoi */
-------------------------------------------------------------------
i found my error only when i had coded it up and ran the program. of course from thinking
about it and drawing the trace and knowing how the disk should move from the constraints,
i found the error quickly. ( here, speaking about the first algorithm where i had written so much )
i'm learning C by self studying. i found this group and it has been great. i feel
as if i am no longer just learning from the book's authors, I actually have teachers.
that said the implementation in C was not bad at all. i don't mind sharing at all. everyone,
here is sharing their knowledge with me, so ... no problem.

(my thought is to do every exercise in the book. it takes some time, but really
there are some things only discussed in the exercises that seem really important
to having a well rounded comp. science start. anyway...)

--------------------------------------------------------------------

/*
Exercise from C How To Program by Deitel and Deitel.
This program is a solution to exercise 5.35 page 190,
that ask for the creation of a program to solve the
Towers of Hanoi. There are constraints as to how the
disk may be placed on the pegs.

The program must use recursion, and the function call must
have the following parameters.

The number of disks to be moved
The peg on which these disks are intially threaded
The peg to which this stack of disk is to be moved
The peg to be used as a temporary holding area

The print out is consistant with what is ask for by the problem:
for example:
1->3 (This means move one disk from peg 1 to peg 3.)
1->2
3->2
1->3
...

This program was written by gdotone, with a tremendous
hint given by Ben of the comp.lang.c (google groups)
*/

#include <stdio.h>

/* prototype */
void solveTowerOfHanoi ( int n, int source, int destination, int temporaryPeg );

int main(int argc, char * argv[])
{
int n; /* number of disk */
int initialPeg; /* starting peg with disc */
int finalPeg; /* where disc should end up */
int tempHoldingPeg; /* temporary Peg */

printf( "This program solves the Tower of Hanoi recursively\n" );

printf( "Enter the number of disc: " );
scanf( "%d", &n );

printf( "Enter the initial peg where disc can be found: " );
scanf( "%d", &initialPeg );

printf( "Enter final peg where disc should end up: " );
scanf("%d", &finalPeg );

printf( "Enter temporary holding peg: " );
scanf( "%d", &tempHoldingPeg );

printf("\n");
printf( "The following means a disk on .#. peg moves to .#. peg.\n\n" );

solveTowerOfHanoi(n, initialPeg, finalPeg, tempHoldingPeg );

return 0;

} /* end main( void ) */

/******************** solveTowerOfHanoi *********************/

void solveTowerOfHanoi ( int n, int source, int destination, int temporaryPeg)
{
if (n == 1)
printf("%d -> %d\n", source, destination);
else
{
solveTowerOfHanoi( n - 1, source, temporaryPeg, destination );
printf( "%d -> %d\n", source, destination );
solveTowerOfHanoi( n - 1, temporaryPeg, destination, source );
} /* end else */

} /* end solveTowerOfHanoi ( int n, int source ... ) */

----------------------------------------------------------------
For this problem, it makes a simple case of putting all the disk on one initial peg.
Actually, the program allows you to decide which peg will be your temporary peg.
Well for example, using 3, 1, 3, 2 gives the same pattern of movement ask by the
exercise in the book. those numbers are the responses used to the programs
prompts.
That's cool. The C program presented here could do the same with a few lines of code.
Actually with a little extra work only the initial peg with all the disk on them really
needs to be inputed. The program could be written to assign the other two pegs for what-
ever purpose. ( a few more line of code, but of course some of the original lines
would not be necessary. may be even a shorter program over all )

g.

G G, Sep 13, 2013
13. ### WillemGuest

Ben Bacarisse wrote:
)<snip>
)> The central function I had, the one similar to yours, looks like this
)> (consider this pseudo-code):
)>
)> proc movediscs(n,a,b)=
)> if n=1 then
)> movedisc(a,b)
)> else
)> c:=thirdpeg(a,b)
)> movediscs(n-1,a,c)
)> movedisc(a,b)
)> movediscs(n-1,c,b)
)> endif
)> end
)
) Things get simpler if you allow for the possibility of moving no discs.

Case in point:

proc movediscs(n,a,b)=
if n>0 then
c:=thirdpeg(a,b)
movediscs(n-1,a,c)
movedisc(a,b)
movediscs(n-1,c,b)
endif
end

)> One difference is that this function works out the temporary peg for itself
)> (you need a function that, given two different values from 1 to 3, returns
)> the third value).
)
) That's the way I like to do it, but it seems to be rare in all the
) presentations I've seen.

Seems wasteful, when you can just pass along the third peg:

proc movediscs(n,a,b,c)=
if n>0 then
movediscs(n-1,a,c,b)
movedisc(a,b)
movediscs(n-1,c,b,a)
endif
end

SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

Willem, Sep 13, 2013
14. ### BartCGuest

Yes, that's neater, although it doesn't change the number of actual discs
that need to be moved. But it seems to double the number of calls needed,
and makes it a bit slower.
That's also neater, in not having to provide the extra bit of logic (at a
cost of having to provide info that it ought to be able to deduce). However
it also makes it a bit faster!

I suppose the temporary peg can be worked out just at the beginning, so the
logic is needed, but the user doesn't need to enter it and it will still be
faster.

BartC, Sep 13, 2013
15. ### Ben BacarisseGuest

Seems wasteful to pass a third argument to a recursive function!! If
'src' and 'dst' hold pegs numbered 1, 2 or 3, then src ^ dst is the spare
peg:

void move(int n_disks, int from_peg, int to_peg)
{
if (n_disks > 0) {
move(n_disks - 1, from_peg, from_peg ^ to_peg);
printf("Move disk from peg %d to peg %d\n", from_peg, to_peg);
move(n_disks - 1, from_peg ^ to_peg, to_peg);
}
}

(You'd probably want to comment that!) Still, wasteful is all
relative...

Ben Bacarisse, Sep 13, 2013
16. ### Ben BacarisseGuest

Is it faster if you number the pegs 1, 2 and 3 and use xor? Actually I
am surprised you can detect any difference in speed given that the
program is likely to be IO bound.

<snip>

Ben Bacarisse, Sep 13, 2013
17. ### Ben BacarisseGuest

No, but Willem has answered for me. In general, you want functions to
work with vacuous cases (empty strings, zero-length arrays, no pegs...).

<snip>

Ben Bacarisse, Sep 13, 2013
18. ### BartCGuest

Using xor was marginally slower, although that might be to do with how my
language works.

But trying it in C in this form:

void hanoi(int n,int a,int b) {
if (n==1) return;
hanoi (n-1, a, a^b);
hanoi (1, a,b);
hanoi (n-1, a^b, b);
}

even this was marginally (1%) slower than providing the extra argument.
Although this version doesn't do any actual work of moving discs around, so
the difference will be negligible. Avoiding an extra argument I think is
more elegant however.
Not really. While it was amusing to display the results at each step,
normally it will only show the results at the beginning and the end.

BartC, Sep 14, 2013
19. ### WillemGuest

Ben Bacarisse wrote:
)> Seems wasteful, when you can just pass along the third peg:
)>
)> proc movediscs(n,a,b,c)=
)> if n>0 then
)> movediscs(n-1,a,c,b)
)> movedisc(a,b)
)> movediscs(n-1,c,b,a)
)> endif
)> end
)
) Seems wasteful to pass a third argument to a recursive function!! If
) 'src' and 'dst' hold pegs numbered 1, 2 or 3, then src ^ dst is the spare
) peg:
)
) void move(int n_disks, int from_peg, int to_peg)
) {
) if (n_disks > 0) {
) move(n_disks - 1, from_peg, from_peg ^ to_peg);
) printf("Move disk from peg %d to peg %d\n", from_peg, to_peg);
) move(n_disks - 1, from_peg ^ to_peg, to_peg);
) }
) }
)
) (You'd probably want to comment that!) Still, wasteful is all
) relative...

Indeed! The waste I was thinking of was the time I would need to
think about a solution to finding the third peg, given the other two.

SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

Willem, Sep 14, 2013
20. ### Ben BacarisseGuest

Ah, I hadn't thought of that. However, for me (and, I suspect, for you
too) it's not a fair fight. Since I was already well-aware of the four
argument version, any thought at all would be a wast of time (and that's
probably the only time I'll ever say that).

Ben Bacarisse, Sep 14, 2013

Ask a Question

## Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.