Tower of Hanoi

This is a discussion on Tower of Hanoi within the C Programming forums, part of the General Programming Boards category; I am working on a problem for school and it involves recursion. My exercise ask me to write a program ...

  1. #1
    Registered User
    Join Date
    Mar 2007
    Posts
    42

    Tower of Hanoi

    I am working on a problem for school and it involves recursion. My exercise ask me to write a program that solves the tower of hanio using recursion. I have gone out and found a number of examples but I am unclear on how the program works. Can someone explain this concept to me? Thanks

    DMKanz07

  2. #2
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,211
    Broad question. Broad answer.

    Note the nice gif image.

    Oh, and there just so happens to be a recursive algorithm located on the page with C code written for you. I doubt you'll be able to copy it directly, but you can definitely learn from it.

  3. #3
    Registered User
    Join Date
    Mar 2007
    Posts
    42
    This is the one example I found. I am not sure I fully understand what is happening in this program. Any guidance would be appreciated.

    Code:
    #include<stdio.h>
    
    /* Function Prototype */
    void towers( int number, int peg1, int peg3, int peg2 );
    
    /* Function main begins program execution */ 
    main()
    {
    
        int number; /* Variable in which number will be stored */
        
        printf( "Enter total no. of disks: " ); /* Prompt for input */
            scanf( "%d",&number ); /* Read number from user */
            towers( number, 1, 3, 2 ); /* Function called */
    
    } /* End function main */
    
    /* Towers function definition */
    void towers( int number, int peg1, int peg3, int peg2 )
    {
    
        if( number == 1 ){
            printf( "%d --> %d\n", peg1, peg2 );
            return; /* Indicates that program ended successfully */
        } /* End if */ 
        
        towers( number - 1, peg1, peg2, peg3 );
            printf( "%d --> %d\n", peg1, peg2 );
        towers( number - 1, peg3, peg1, peg2 );
        
    } /* End function towers */
    The output for 3 disk is
    1 --> 2
    1 --> 3
    2 --> 3
    1 --> 2
    3 --> 1
    3 --> 2
    1 --> 2

    Can you explain the function and how it knows what number goes where? This is very confusing to me.

    Thank you

    DMKanz07

  4. #4
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,211
    Perhaps before you go any further with programming stuff like this, you should make sure you understand how the algorithm works.

    For example, can you intuitively do the solution "by hand"? If so, can you then express the algorithm in English (or any other natural language) step by step? If so, then work on translating your natural language instructions into C.

    For me personally, I never liked pseudo code and I hated listing all of my steps out. I rarely (never?) do that before starting a program, but I do think the program through and try to have an entire idea of how I'm going to get it done before I even start. If I get stuck on something not working or something difficult, I'll manually trace it out on paper and draw all kinds of notations that I'm unsure that anyone else can read.

    Now with that said, is your problem related to the Towers of Hanoi problem, or is it related to recursion?

    The numbers are just showing when to move the ring from tower x to tower y. That particular list of numbers, I believe, will get you from all of the rings on tower 1 to tower 2.

  5. #5
    Registered User
    Join Date
    Mar 2007
    Posts
    42
    You been very helpful thanks

    DMKanz07

  6. #6
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Been awhile, but in the Towers of Hanoi, there's a simple trick:

    If the pile of disks you want to move is odd, then move the first disk to the peg you want them to rest upon, when that stack or sub stack, is completely moved. If the number of disks you need to move is even, then move the first disk to the peg you DO NOT want them to ultimately rest upon.

    The thing with the game that's tough is that in order to make a move with more disks, you have to make more "sub stacks", in order to complete your move. It's hard to remember which sub stack needs to be moved next and in general, just where you are in the order of moves and sub-moves, that are needed to win the game.

    Always remember the odd and even trick though - it's true for all moves, and for all the little sub moves you make, anywhere in the course of the game.

    So if you have 3 disks, on the leftmost peg, and you want to move those disks to the center peg ultimately, move the first disk on your first move, from the leftmost peg to the center peg, Next disk move is left to right, then center to right, then left to center.

    Now you have to move a 2 disk sub stack to move from right to center. Since it's an even number of disks to be moved, move is right to left (away from final goal peg), then right to center, and finally left to center.

    If you have a lot of disks to move, it helps if they're numbered or REALLY have large steps in their sizes, to easily keep track of each sub stack, and not get mucked up by taking one disk to many or too few, on a sub stack move.

    Adak
    Last edited by Adak; 03-29-2007 at 04:53 AM.

  7. #7
    Lean Mean Coding Machine KONI's Avatar
    Join Date
    Mar 2007
    Location
    Luxembourg, Europe
    Posts
    444
    What I find incredibly amazing about the Towers of Hanoi problem is how simple the reasoning behind the recursive algorithm is. You can sit there and think about the solution for hours without grasping the concept:

    To move n disks from peg A to peg B:
    • Move n−1 disks from A to C. This leaves the nth disk alone on peg A;
    • Move the nth disk from A to B;
    • Move n−1 disks from C to B so they sit on the nth disk.


    That's all you need to know. Think about it, understand it (!) and then write it.

  8. #8
    Registered User
    Join Date
    Mar 2007
    Posts
    42
    I am comfortable with how you make the moves. What I am confused on is how does the program know what number to display in the output.

    towers( number - 1, peg1, peg2, peg3 );
    printf( "%d --> %d\n", peg1, peg2 );
    towers( number - 1, peg3, peg1, peg2 );

    In the printf statement it calls for peg1 and peg2. The first move is 1 --> 2 the second move is 1 --> 3. Why would this not repeat 1 --> 2. I am looking for an explanation on the syntax of the function. I hope this make sense. Still learning C

    Thanks

    DMKanz07

  9. #9
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,434
    If you gave the variables better names, say like this

    towers( number - 1, from, spare, to ); // move n-1 to the spare, using 'to' as a workspace
    printf( "&#37;d --> %d\n", from, to ); // move the bottom disk
    towers( number - 1, spare, to, from ); // move n-1 from the spare, using 'from' as the workspace

    Does that help visualise the problem?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  10. #10
    Registered User
    Join Date
    Mar 2007
    Posts
    42
    not really

    again how does the function print a 1, 2 or 3 if the printf statement is calling for from and to variable

    this is very confusing to me - sorry

    thanks

    dmkanz07

  11. #11
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,434
    Well single step the code with a tower of two disks.
    Then do it with 3 disks.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  12. #12
    Lean Mean Coding Machine KONI's Avatar
    Join Date
    Mar 2007
    Location
    Luxembourg, Europe
    Posts
    444
    Look in the code, where the function is called the first time:
    Code:
    towers( number, 1, 3, 2 ); /* Function called */
    Here, you're actually attributing the numbers to the different parameters, which will later on be printed out.

  13. #13
    Registered User
    Join Date
    Mar 2007
    Posts
    42
    Does it reassign values to from and to each time thru the recursion until number == 1. If so, in the first part of the functions is it safe to assume that if you have three disk that it reads

    tower(number-1, from, to, spare) = tower( 3-1, 1, 2, 3)

    is this correct

    Thanks

    DMKanz07

  14. #14
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by dmkanz07 View Post
    Does it reassign values to from and to each time thru the recursion until number == 1. If so, in the first part of the functions is it safe to assume that if you have three disk that it reads

    tower(number-1, from, to, spare) = tower( 3-1, 1, 2, 3)

    is this correct

    Thanks

    DMKanz07
    All recursive functions have a base case so it can figure out when to stop. You probably DON'T want to label the pegs from, to, and spare, because the from to and spare will change with the move, and maybe it won't confuse the computer, but it darn sure will confuse the poor human!

    In parameter passing, it is done by THEIR ORDER in the parameter list - NOT by their name. So a parameter of (peg1, peg2) may be received by the functions with (peg_1, peg_2), but if I change the calling parameters to (peg3, peg2), and keep the receiving parameters the same, now peg3 will be copied into the receiving functions peg_1, and the second parameter will be copied into the second receiving functions parameter of peg_2.

    Remember that ALL parameters in C are passed by a copy mechanism, not the actual parameter itself. Pointers APPEAR to be passing the same parameter, but they don't, either. It just LOOKS like they do, because the copied memory address received by the function, is just as good as the original, so IN EFFECT, it's a call which includes the original parameter - but it's not.

    Say you have a variable int number in main(), and you call another function like this:
    AnotherFunction(number);

    Now in AnotherFunction, the variable "number", is NOT the same variable as the "number" variable in main(). It is a copy, and if AnotherFunction wants to receive that copied "number" variable, with another name, it's perfectly free to do so:
    void AnotherFunction(int AliasNameForNumberInMain)

    Hope that helps.

    Adak
    Last edited by Adak; 03-29-2007 at 12:40 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. towers of hanoi problem
    By aik_21 in forum C Programming
    Replies: 1
    Last Post: 10-02-2004, 01:34 PM
  2. Little Problem on Presentation in the Tower of Hanoi
    By momegao in forum C++ Programming
    Replies: 3
    Last Post: 04-20-2003, 06:22 PM
  3. Tower of Hanoi
    By carrja99 in forum C++ Programming
    Replies: 2
    Last Post: 02-09-2003, 11:15 AM
  4. Hanoi tower
    By Unregistered in forum C Programming
    Replies: 3
    Last Post: 04-24-2002, 06:35 PM
  5. Tower Of Hanoi
    By Unregistered in forum C Programming
    Replies: 7
    Last Post: 12-18-2001, 10:12 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21