Towers of Hanoi

This is a discussion on Towers of Hanoi within the C Programming forums, part of the General Programming Boards category; I have to use recursion (evil evil... for me anyhow) to make a Towers of Hanoi program. Towers of Hanoi ...

  1. #1
    Registered User
    Join Date
    Oct 2001
    Posts
    2

    Towers of Hanoi

    I have to use recursion (evil evil... for me anyhow) to make a Towers of Hanoi program. Towers of Hanoi is where you have those 3 pins. The user enters the number of disks, and the program prints in order "Move disk # from pin # to pin #". Right now, I can get about half the stack moved correctly, then after that, it begins giving me bogus input... any ideas how to go about making this program because i'm totally lost!

  2. #2
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    Check the thread, "When to use recursion?"
    Callou collei we'll code the way
    Of prime numbers and pings!

  3. #3
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    search these boards and you will find some code to learn from. We have done this before.

    here is an iterative solution..... lol

    Code:
    #include <stdio.h>
    
    int main() {
      long z,y,n;
    
      scanf("%d",&n);
      for(y=1;(1<<n)-y; y<<=z-1,
                         printf("disk %i from %i to %i.\n",z,(y&y-1)%3,((y|y-1)+1)%3), 
                         y++)
       for(z=1; !(y&1); z++,
                        y>>=1);
       return 0;
    }
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

  4. #4
    Unregistered
    Guest
    Hi,

    My book also tells me to solve the problem of Towers of Hanoi and i skipped that bit coz it's already too hard to do it for real, like by hand as if there's a real toy in front of me lol.

    But it'll good if someone post the recursion solution for me to study.

    thnx

  5. #5
    Unregistered
    Guest
    Hey wait i found the solution!

    Code:
    void hanoi (int src, int aux, int dest, int num)
    {
     if (num != 0)
     {
      // Move the pegs above to the auxillary peg...
      hanoi (src, dest, aux, num - 1);
      
      // Move the current peg to the destination peg...
      printf ("Peg moved from %d to %d.\n", src, dest);
    
      // Move the pegs from the auxillary peg to dest
      hanoi (aux, src, dest, num - 1);
     }
     return;
    }

  6. #6
    Unregistered
    Guest
    Wait sorry thats not my code, got it off somewhere. But i havce one question. If all disks are to be moved to peg 3 and uses peg 2 as a temporary holding area ( that means there are 3 pegs together ), then why don't you just move all the disk one by one to disk 2 and one by one again to peg 3?

    anyway, i can't figure out the function either!

  7. #7
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    like I said. search these boards you lazy sod.....

    this is what i was telling you about earlier.
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

  8. #8
    Registered User zahid's Avatar
    Join Date
    Aug 2001
    Posts
    532

    Solution

    /* t_of_hanoi.c */

    #include<stdio.h>
    int shift(int, int, int);

    int main()
    {
    int disk;

    printf("Number of disk:");
    scanf("%d",&disk);

    shift_disk(1,3,disk);

    }


    int shift_disk(int from, int to, int disk)
    {
    /* 1,2,3 are the towers*/
    int new_to;
    new_to= from+to;

    new_to = 6-new_to;
    if(disk==0) return 0;


    /* first move all except the last */
    /*to the mid tower*/
    shift_disk(from, new_to, disk-1);

    printf("Move a disk from tower %d to %d\n",from,to);

    /*Then move all disks from mid tower*/
    /* to destination tower*/
    shift_disk(new_to, to, disk-1);

    return 0;

    }
    [ Never code before desk work ]
    -------------------------------------:-->
    A man who fears Nothing is the man who Loves Nothing
    If you Love Nothing, what joy is there in your life.
    =------------------------------------------------------= - I may be wrong.

  9. #9
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    This might help you somewhat. Probably
    best to do this with pencil and paper.

    Code:
    #include <stdio.h>
    
    #define N 3
    #define NR_STACKS 3
    
    static int disk_stack[NR_STACKS] = { N, 0, 0 };
    
    int max(int a[], int n)
    {
        int i;
        int greatest = a[0];
    
        for (i = 1; i < n; ++i) 
            if (a[i] > greatest)
                greatest = a[i];
    
        return greatest;
    }
    
    void print_disk_stack()
    {
        int i, j;
        
        j = max(disk_stack, NR_STACKS);
        for (; j > 0; --j) {
            for (i = 0; i < NR_STACKS; ++i) {
                if (disk_stack[i] >= j)
                    putchar('*');
                else
                    putchar(' ');
            }
            putchar('\n');
        }
    
        putchar('\n');
    }
    
    void hanoi(int src, int aux, int dst, int num)
    {
        if (num == 1) {        
            print_disk_stack();
            printf("(%d, %d)\n", src, dst);
            disk_stack[src]--;
            disk_stack[dst]++;        
        } else {
            hanoi(src, dst, aux, num-1);
            hanoi(src, aux, dst, 1);
            hanoi(aux, src, dst, num-1);
        }
    }
    
    
    int main(void)
    {
        hanoi(0, 1, 2, N);
        print_disk_stack();
    
        return 0;
    }

  10. #10
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    thnx

    To Zahid:

    Why call the function twice in that function ?
    I am very confused. Are you guys all good at maths and stuff?

  11. #11
    Registered User zahid's Avatar
    Join Date
    Aug 2001
    Posts
    532
    I have divided the solution into two parts:

    If I want to move the bottom disk of first tower to my destination tower (Third Tower).

    => First I have to move all except the bottom disk to the second tower.

    =>Now time to move the target disk. (1 step)

    => Then I have to move all of second to third tower.

    Isn't it very simple to think in this way?
    This is actually the reflaction of my thinking to solve the problem.
    Last edited by zahid; 01-07-2002 at 12:46 AM.
    [ Never code before desk work ]
    -------------------------------------:-->
    A man who fears Nothing is the man who Loves Nothing
    If you Love Nothing, what joy is there in your life.
    =------------------------------------------------------= - I may be wrong.

  12. #12
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    Your signature says 'Never code before desk work', and i'm very new to c and had many problems, so can you post your pseudocode here for me to study if it's possible?

    thnx

  13. #13
    Registered User zahid's Avatar
    Join Date
    Aug 2001
    Posts
    532
    Welcome to CBOARD....
    You can say my previous posting was a pseudocode for Tower of Hanoi Problem...
    [ Never code before desk work ]
    -------------------------------------:-->
    A man who fears Nothing is the man who Loves Nothing
    If you Love Nothing, what joy is there in your life.
    =------------------------------------------------------= - I may be wrong.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. towers of hanoi - what is wrong with this code?
    By kanesoban in forum C Programming
    Replies: 4
    Last Post: 09-17-2007, 02:20 PM
  2. Towers of Hanoi (need help)
    By Loudan in forum C++ Programming
    Replies: 3
    Last Post: 01-30-2006, 10:17 PM
  3. towers of hanoi problem
    By aik_21 in forum C Programming
    Replies: 1
    Last Post: 10-02-2004, 02:34 PM
  4. Towers of Hanoi
    By cyberCLoWn in forum C++ Programming
    Replies: 6
    Last Post: 01-15-2004, 04:28 PM
  5. Towers of Hanoi, special output.
    By spoon_ in forum C Programming
    Replies: 3
    Last Post: 03-15-2003, 06:08 PM

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