You have three small poles and five hoops - XS, S, M, L, XL (as in extra small, small, medium, large and extra large). They are placed on pole 1 in order, with largest at the bottom.

You can move one hoop at a time, and the hoops you are not moving have to be on a pole. You also cannot place a hoop on top of a smaller one. How can you move the hoops so that they are in the same order as they are now, but on pole 3?

Here is the solution I was talking about in my previous post (which makes the functions I involved actually useful). There are three stacks of lettered hoops, which are popped off and pushed onto the other poles as each move is made.

This allows for a physical representation of the state of the poles at any time, as well as listing the individual moves:

#include <iostream>
#include <stack>
using namespace std;

void hanoi(int n, int src, int dst, int xtr);
void move(int src, int dst);
void display();

stack <char> p1, p2, p3;
stack <char> *poles[3]={&p1, &p2, &p3};
int num;

void main() {
   cout << "Number of hoops: ";
   cin >> num;
   for (int h=num; h>0; h--) {
      char c=h+64;
      (*poles[0]).push(c);
   }
   cout << endl;
   display();
   cout << "Starting position\n\n";
   hanoi(num, 0, 2, 1);
}

void hanoi(int n, int src, int dst, int xtr) {
   if (n==1) {
      move(src, dst);
      return;
   }
   hanoi(n-1, src, xtr, dst);
   move(src, dst);
   hanoi(n-1, xtr, dst, src);
}

void move(int src, int dst) {
   char x;
   x=(*poles[src]).top();
   (*poles[src]).pop();
   (*poles[dst]).push(x);
   display();
   cout << "Move hoop " << x << " from pole " << ++src
   cout << " to pole " << ++dst << "\n\n";
}

void display() {
   stack <char> t1=*poles[0], t2=*poles[1], t3=*poles[2];
   stack <char> *temp[3]={&t1, &t2, &t3};
   for (int row=num; row>0; row--) {
      for (int p=0; p<3; p++) {
         cout << "  ";
         if ((*temp[p]).size()<row)
            cout << "|";
         else {
            cout << (*temp[p]).top();
            (*temp[p]).pop();
         }
      }
      cout << endl;
   }
}

Sample output:

Number of hoops: 3

  A  |  |
  B  |  |
  C  |  |
Starting position

  |  |  |
  B  |  |
  C  |  A
Move hoop A from pole 1 to pole 3

  |  |  |
  |  |  |
  C  B  A
Move hoop B from pole 1 to pole 2

  |  |  |
  |  A  |
  C  B  |
Move hoop A from pole 3 to pole 2

  |  |  |
  |  A  |
  |  B  C
Move hoop C from pole 1 to pole 3

  |  |  |
  |  |  |
  A  B  C
Move hoop A from pole 2 to pole 1

  |  |  |
  |  |  B
  A  |  C
Move hoop B from pole 2 to pole 3

  |  |  A
  |  |  B
  |  |  C
Move hoop A from pole 1 to pole 3

And, the requested case with n=5:

Number of hoops: 5

  A  |  |
  B  |  |
  C  |  |
  D  |  |
  E  |  |
Starting position

  |  |  |
  B  |  |
  C  |  |
  D  |  |
  E  |  A
Move hoop A from pole 1 to pole 3

  |  |  |
  |  |  |
  C  |  |
  D  |  |
  E  B  A
Move hoop B from pole 1 to pole 2

  |  |  |
  |  |  |
  C  |  |
  D  A  |
  E  B  |
Move hoop A from pole 3 to pole 2

  |  |  |
  |  |  |
  |  |  |
  D  A  |
  E  B  C
Move hoop C from pole 1 to pole 3

  |  |  |
  |  |  |
  A  |  |
  D  |  |
  E  B  C
Move hoop A from pole 2 to pole 1

  |  |  |
  |  |  |
  A  |  |
  D  |  B
  E  |  C
Move hoop B from pole 2 to pole 3

  |  |  |
  |  |  |
  |  |  A
  D  |  B
  E  |  C
Move hoop A from pole 1 to pole 3

  |  |  |
  |  |  |
  |  |  A
  |  |  B
  E  D  C
Move hoop D from pole 1 to pole 2

  |  |  |
  |  |  |
  |  |  |
  |  A  B
  E  D  C
Move hoop A from pole 3 to pole 2

  |  |  |
  |  |  |
  |  |  |
  B  A  |
  E  D  C
Move hoop B from pole 3 to pole 1

  |  |  |
  |  |  |
  A  |  |
  B  |  |
  E  D  C
Move hoop A from pole 2 to pole 1

  |  |  |
  |  |  |
  A  |  |
  B  C  |
  E  D  |
Move hoop C from pole 3 to pole 2

  |  |  |
  |  |  |
  |  |  |
  B  C  |
  E  D  A
Move hoop A from pole 1 to pole 3

  |  |  |
  |  |  |
  |  B  |
  |  C  |
  E  D  A
Move hoop B from pole 1 to pole 2

  |  |  |
  |  A  |
  |  B  |
  |  C  |
  E  D  |
Move hoop A from pole 3 to pole 2

  |  |  |
  |  A  |
  |  B  |
  |  C  |
  |  D  E
Move hoop E from pole 1 to pole 3

  |  |  |
  |  |  |
  |  B  |
  |  C  |
  A  D  E
Move hoop A from pole 2 to pole 1

  |  |  |
  |  |  |
  |  |  |
  |  C  B
  A  D  E
Move hoop B from pole 2 to pole 3

  |  |  |
  |  |  |
  |  |  A
  |  C  B
  |  D  E
Move hoop A from pole 1 to pole 3

  |  |  |
  |  |  |
  |  |  A
  |  |  B
  C  D  E
Move hoop C from pole 2 to pole 1

  |  |  |
  |  |  |
  |  |  |
  |  A  B
  C  D  E
Move hoop A from pole 3 to pole 2

  |  |  |
  |  |  |
  |  |  |
  B  A  |
  C  D  E
Move hoop B from pole 3 to pole 1

  |  |  |
  |  |  |
  A  |  |
  B  |  |
  C  D  E
Move hoop A from pole 2 to pole 1

  |  |  |
  |  |  |
  A  |  |
  B  |  D
  C  |  E
Move hoop D from pole 2 to pole 3

  |  |  |
  |  |  |
  |  |  A
  B  |  D
  C  |  E
Move hoop A from pole 1 to pole 3

  |  |  |
  |  |  |
  |  |  A
  |  |  D
  C  B  E
Move hoop B from pole 1 to pole 2

  |  |  |
  |  |  |
  |  |  |
  |  A  D
  C  B  E
Move hoop A from pole 3 to pole 2

  |  |  |
  |  |  |
  |  |  C
  |  A  D
  |  B  E
Move hoop C from pole 1 to pole 3

  |  |  |
  |  |  |
  |  |  C
  |  |  D
  A  B  E
Move hoop A from pole 2 to pole 1

  |  |  |
  |  |  B
  |  |  C
  |  |  D
  A  |  E
Move hoop B from pole 2 to pole 3

  |  |  A
  |  |  B
  |  |  C
  |  |  D
  |  |  E
Move hoop A from pole 1 to pole 3

Edited on September 9, 2003, 12:33 am

Posted by DJ on 2003-09-08 13:28:35