Solve Towers of Hanoi with 10 plates recursive c++

Question

Trying to solve Towers of Hanoi, and i really can't understand why my function won't work. I have checked every c++ solution in here.

bool CPlayer::MoveTop(int n, int from, int to)
{
    if (n == 0)
    {
        m_towers.MoveDisc(to, 1);
        return true;
    }

    MoveTop(n -1 , from , 1);

    m_towers.MoveDisc(1,from);

    MoveTop(n - 1, 1, to);

}// MoveTop

Where 1 is the middle peg. And m_tower.MoveDisc(to,from) moves one disc from one peg to another.

And here is the first call to the function MoveTop.

void CPlayer::OnRun()
{
    bool ok = MoveTop(10,0,2);

}// OnRun

I also got a Height function that returns numbers of plates on called peg, but i don't really think I need it.

ADDED MORE PROBLEM DESCRIBING All of the moves are shown in a graphic window where I can see the result of how the plates are moved from peg to peg. And now, it won't simply do what it should. When running the code the first plat moves to peg 1 (the peg in the middle) and "jumps" up and down.

These are the functions available:

The Height function:

int CTowers::Height(int tower)
{
    ASSERT( torn>=0 && torn<3 );

    return m_height[torn];
}

Returns Height on specific tower.

int CTowers::TopSize(int tower)
{

        int h = Height(tower);
        if (h==0)
            return 1000;
        else return DiscSize(torn, h-1);
}

Returns the size of top on peg.

int CTowers::DiscSize(int tower, int place)
{
    ASSERT( place < Height(torn) );

    return m_pinne[tower][place];
}

Returns specified dicssize.

bool CTowers::MoveDisc(int to, int from)
{
  if (m_abort)
      return false;   //    

  m_pView->DrawAnimation( from, to );

  if (TopSize(from)>=TopSize(to))
        return false;
  m_numMoves++;
  int ds = Pop(from);
  Push(to, ds );
  m_pView->Invalidate();
  return true;
}

Moves a disc from one peg to another.

Answer 1

This is an old school :) divide & conquer problem.

Try looking at this code:

void hanoi(int diskSize, int source, int dest, int spare)
{
  //This is our standard termination case. We get to here when we are operating on the 
  //smallest possible disk.
  if(diskSize == 0)
    {
        std::cout << "Move disk " << diskSize << " from peg " << source << " to peg " << dest << endl;
    }
    else
    {
        //Move all disks smaller than this one over to the spare.
        //So if diskSize is 5, we move 4 disks to the spare. This leaves us with 1 disk
        //on the source peg.
        //Note the placement of the params.
        //We are now using the dest peg as the spare peg. This causes each recursion to ping-pong
        //the spare and dest pegs.
        hanoi(diskSize - 1, source, spare, dest);

        //Move the remaining disk to the destination peg.
        std::cout << "Move disk "  << diskSize << " from peg " << source << " to peg " << dest << endl;

        //Move the disks we just moved to the spare back over to the dest peg.
        hanoi(diskSize - 1, spare, dest, source);
    }
}

The idea of having 3 arguments (source, dest, spare) is to be able to know at each time which peg is the spare one so that you can use it for putting disks on it.

As stated in the comments, the recursion ping-pongs between the spare and the dest.

Your code cannot respect the rule where you cannot put a larger disk on top of a smaller disk (see here). So you need a variable to keep the target peg which is not always 1 like in your code.

That's why you need 3 arguments.

Cheers!