linear towers of hanoi

Question

I have a question on the linear Towers of Hanoi.

I implemented it in C++ but am trying to do the same using the tail recursive or iterative method. I am having trouble with my algorithm.

This code snippet shows transferring blocks from the middle tower to the end tower.

#include <stdlib.h>
#include <stdio.h>
using namespace std;

//int a[5]={2,3,1,2,1};
int from,spare,to;

int main()
{
//int n;

//void hanoi(int,int,int,int);
void linear_hanoi(int,int,int,int);
void mid_to_end(int,int,int,int);
void end_to_mid(int,int,int,int);
//mid_to_end(3,2,3,1);
end_to_mid(4,3,2,1);
getchar();
return 0;
}

void linear_hanoi(int n, int from, int to, int spare)
{
     if(n>0)
      {
            linear_hanoi(n-1,from,to,spare);
            cout<<"move ring "<<n<<" from tower "<<from<<" to tower "<<spare<<endl;
            linear_hanoi(n-1,to,from,spare);
            cout<<"move ring "<<n<<" from tower "<<spare<<" to tower "<<to<<endl;
            linear_hanoi(n-1,from,to,spare);
      }
}
void mid_to_end(int n, int from, int to, int spare)
{
  if(n>0)
  {
     mid_to_end(n-1,from,spare,to);
     cout<<"move ring "<<n<<" from tower "<<from<<" to tower "<<to<<endl;
    // mid_to_end(n-1,spare,from,to);
   //  mid_to_end(n-1,from,to,spare);
   //cout<<"move ring "<<n<<" from tower "<<spare<<" to tower "<<from<<endl;
  // mid_to_end(n-1,from,to,spare);
    //cout<<"move ring "<<n<<" from tower "<<spare<<" to tower "<<from<<endl;
 }
}

What am I doing wrong?

Answer 1

From wikipedia:

Simple solution: The following solution is a simple solution for the toy puzzle.

Alternate moves between the smallest piece and a non-smallest piece. When moving the smallest piece, always move it in the same direction (to the right if the starting number of pieces is even, to the left if the starting number of pieces is odd). If there is no tower in the chosen direction, move the piece to the opposite end, but then continue to move in the correct direction. For example, if you started with three pieces, you would move the smallest piece to the opposite end, then continue in the left direction after that. When the turn is to move the non-smallest piece, there is only one legal move. Doing this should complete the puzzle using the least amount of moves to do so.

Answer 2

You can transform the code into continuation-passing-style. Then everything is tail-recursive...