Tower of hanoi problem

Question

Hi Guys I am faced with a problem on tower of hanoi:
we are given a stack of cylinders of alternate colors stacked over one another alternately.
The job is to separate the two stacks of same colour
I could write the code(algorithm) for a regular tower of hanoi using recursion, but I am not able to figure out this part. Can some one help?
Code for regular hanoi problem:

#include<iostream>

using namespace std;
int count=0;

void hanoi(char a,char b,char c,int x)
{
  if(x>1)
  {
    hanoi(a,c,b,x-1);
    hanoi(a,b,c,1);
    hanoi(c,b,a,x-1);
  }
  else
  {
    cout<<"Move a Disk from "<<a<<" to "<<b<<endl; count++;  
  }
}

int main()
{
  int n;
  cout<<"Enter the height of stack";
  cin>>n;
  hanoi('A','B','C',n);
  cout<<"\nNo. of changes done:"<<count;

  return 0;
}

You should really format your code in a more structured manner. There is zero indentation in what you pasted and its tough to read, even though I know exactly how this solution works. — BSchlinker, Apr 26 '11 at 20:27
@Frustated Coder: **indent your code** /8-/ <<-- Stern looking face. — Johan, Apr 26 '11 at 20:29
how many towers and what are the restrictions? If 3 towers and no restrictions of positioning rings on one another, as it sounds from your question, than it is trivial - just move each ring to tower 2 or 3 according to its color — davka, Apr 26 '11 at 20:30
@asgs, you edited the post and fixed some typos in the code, please **do not do that** if these is a problem in the code that is caused by these typos, answerers are unable to see these and unable to point this out, confusing everybody. — Johan, Apr 26 '11 at 20:32
Homework? I mean i worked out regular hanoi problem but stuck at this colour problem — Frustrated Coder, Apr 26 '11 at 20:33
@Frustated coder, you indent by putting 2 (and only 2) spaces before every new block. A block is started by `{` and ended by `}`. Also if you have a line that does not fit on the screen so you put an enter in there you indent the second line with 2 spaces to show that it belongs with the first line and is not an independent item. — Johan, Apr 26 '11 at 20:35
@Frustated coder, O and if you want you code to **look like code** select all of it and then press ctrl+K, if you click on the orange "?" in the right top of the edit screen thingy you can see all the help about layout. — Johan, Apr 26 '11 at 20:36
@Johan, please accept my apologies. I didn't mean to mod the code. — asgs, Apr 26 '11 at 21:14
you should check out [this answer in - Tower of Hanoi: Recursive Algorithm](https://stackoverflow.com/a/58259294/7541700) — costargc, Oct 06 '19 at 17:44

riwalk · Accepted Answer · 2011-04-26T20:52:11.450

Solve the problem n times, alternating pegs that you leave the solution on.

int main()
{
    int n;
    cout<<"Enter the height of stack";
    cin>>n;

    char startPeg = 'A';
    char interPeg = 'B';
    char slnPeg = 'C';

    while(n > 0) {
        hanoi(startPeg,interPeg,slnPeg,n);
        n--;
        char temp = startPeg;
        startPeg = slnPeg;
        slnPeg = temp;
    }

    return 0;
}

Here's how it works. Say that our stack has the colors Red(R) and Yellow(Y) and it is 5 units tall:

     |           |           |
    Y|Y          |           |
   RR|RR         |           |
  YYY|YYY        |           |
 RRRR|RRRR       |           |
YYYYY|YYYYY      |           |

After the first run, it looks like this:

     |           |           |
     |           |          Y|Y    
     |           |         RR|RR
     |           |        YYY|YYY
     |           |       RRRR|RRRR
     |           |      YYYYY|YYYYY

After the second run, it looks like this:

     |           |           |    
    Y|Y          |           |
   RR|RR         |           |
  YYY|YYY        |           |
 RRRR|RRRR       |      YYYYY|YYYYY

After the third run, it looks like this:

     |           |           |    
     |           |          Y|Y
     |           |         RR|RR
     |           |        YYY|YYY
 RRRR|RRRR       |      YYYYY|YYYYY

After the forth run, this:

     |           |           |    
     |           |           |
    Y|Y          |           |
   RR|RR         |        YYY|YYY
 RRRR|RRRR       |      YYYYY|YYYYY

After the fifth and final run, this:

     |           |           |    
     |           |           |
     |           |          Y|Y
   RR|RR         |        YYY|YYY
 RRRR|RRRR       |      YYYYY|YYYYY

And at this point you're done.

If you are desperate for recursion, do this:

void painful(char start, char inter, char sln, int n) {
    if(n == 0) return;
    hanoi(start,inter,sln);
    painful(sln,inter,start,n-1);
}

int main()
{
    int n;
    cout<<"Enter the height of stack";
    cin>>n;

    painful('A','B','C',n);

    return 0;
}

You have to run it `n` times, so yes the loop is required. Use whatever kind of loop you want. If you enjoy torturing those after you, you could also use recursion. — riwalk, Apr 26 '11 at 20:41
ya...so how do i use recursion completely in this and eliminate while? I would be grateful to u if u could help me on that — Frustrated Coder, Apr 26 '11 at 20:49
@FrustratedCoder, there's a recursive solution now. I assume it is because of a homework requirement that you have to do this. Don't do it in the real world, as recursion can quickly (and unnecessarily) fill the stack. — riwalk, Apr 26 '11 at 20:52
@DeadMG, the middle pole is used by the function `hanoi()`. This is an algorithm based on the assumption that that function already works, and that function uses 3 poles. — riwalk, Apr 27 '11 at 00:57

score 0 · Answer 2 · edited Dec 04 '15 at 23:15

#include <stdio.h>
hanoi(char a, char b, char c, int h) {
    if(h<=1){
        printf("move:%c to %c :\n", a, b );
    }else{
        hanoi(a,c,b, h-1);
        hanoi(a,b,c, 1);
        hanoi(c,b,a, h-1);
    }
}
main(){
    int input;
    int i ;
    scanf("%d", &input);
    /* A is the src and B is dest */
    for(i=1; i< input ; i++){
        if(i%2){
            hanoi('A', 'B', 'C', input-i);
        }else{
            hanoi('B', 'A', 'C', input-i);
        }
    }
}
// work ?

Tower of hanoi problem

2 Answers2