Towers of Hanoi

• 01-06-2002
janehung
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!
• 01-06-2002
QuestionC
Check the thread, "When to use recursion?"
• 01-06-2002
Stoned_Coder
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; }```
• 01-06-2002
Unregistered
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
• 01-06-2002
Unregistered
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; }```
• 01-06-2002
Unregistered
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!
• 01-06-2002
Stoned_Coder
like I said. search these boards you lazy sod.....

this is what i was telling you about earlier.
• 01-06-2002
zahid
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;

}
• 01-06-2002
Nick
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; }```
• 01-06-2002
Nutshell
thnx

To Zahid:

Why call the function twice in that function ?
I am very confused. Are you guys all good at maths and stuff?
• 01-06-2002
zahid
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.
• 01-06-2002
Nutshell
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
• 01-07-2002
zahid
Welcome to CBOARD....
You can say my previous posting was a pseudocode for Tower of Hanoi Problem...