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!

Check the thread, "When to use recursion?"

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;
}

---

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

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;
}

---

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!

like I said. search these boards you lazy sod.....

this is what i was telling you about earlier.

/* 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;

}

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;
}

---

thnx

To Zahid:

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

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.

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

Welcome to CBOARD....
You can say my previous posting was a pseudocode for Tower of Hanoi Problem...