C++ recursice program to solve Tower of Hanoi puzzle.

Sample Input:

In:
4
Out:
0. Moved disc 1 from tower 0 to tower 1
1. Moved disc 2 from tower 0 to tower 2
2. Moved disc 1 from tower 1 to tower 2
3. Moved disc 3 from tower 0 to tower 1
4. Moved disc 1 from tower 2 to tower 0
5. Moved disc 2 from tower 2 to tower 1
6. Moved disc 1 from tower 0 to tower 1
7. Moved disc 4 from tower 0 to tower 2
8. Moved disc 1 from tower 1 to tower 2
9. Moved disc 2 from tower 1 to tower 0
10. Moved disc 1 from tower 2 to tower 0
11. Moved disc 3 from tower 1 to tower 2
12. Moved disc 1 from tower 0 to tower 1
13. Moved disc 2 from tower 0 to tower 2
14. Moved disc 1 from tower 1 to tower 2

Code:

Updated Version:

// © 2017 TheFlyingKeyboard and released under MIT License
// theflyingkeyboard.net

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

class Tower {
public:
  Tower(stack<int> discs) {
    _discs = discs;
  }

  Tower(int disc0) {
    _discs.push(0);
  }

  //Getters
  int getTopDisc() {
    return _discs.top();
  }

  bool placeDisc(int disc) {
    if (canPlaceDisc(disc)) {
      _discs.push(disc);

      return true;
    }

    return false;
  }

  void removeTopDisc() {
    _discs.pop();
  }

private:
  stack<int> _discs;

  bool canPlaceDisc(int disc) {
    if (_discs.top() > disc || _discs.top() == 0) {
      return true;
    }

    return false;
  }
};


int main() {
  stack<int> discs;
  vector<Tower> towers;

  const int towerNumber = 3;
  int discNumber;

  cout << "Hanoi solver iterative algorithm" << endl;
  cout << "TheFlyingKeyboard.net 2017" << endl;
  cout << "Enter number of discs: ";
  cin >> discNumber;

  discs.push(0);

  for (int i = discNumber; i > 0; i--) {
    discs.push(i);
  }

  towers.push_back(Tower(discs));

  for (int i = 0; i < towerNumber - 1; i++) {
    towers.push_back(Tower(0));
  }

  int smallestDisc;
  int smallestDiscPosition;

  for (int i = 0; i < (1U << discNumber) - 1; i++) {
    cout << i << ". ";

    if (i % 2 == 0) {
      for (int j = 0; j < towerNumber; j++) { 
        if (towers[j].getTopDisc() == 1) { //Find smallest disc and move it to next tower 
          towers[j].removeTopDisc();
          cout << "Moved disc 1 from tower " << j << " to tower ";

          if (j == towerNumber - 1) {					
            towers[0].placeDisc(1);
            cout << "0";				
          }
          else {
            towers[j + 1].placeDisc(1);
            cout << j + 1;
          }

          cout << endl;
          
          break;
        }
      }
    }
    else { //Move smallest disc, which is not disc 1 to valid place
      smallestDisc = discNumber + 1;
      smallestDiscPosition = 0;

      for (int j = 0; j < towerNumber; j++) {
        if (towers[j].getTopDisc() < smallestDisc && towers[j].getTopDisc() != 1 && towers[j].getTopDisc() != 0) {
          smallestDisc = towers[j].getTopDisc();
          smallestDiscPosition = j;
        }
      }

      for (int j = 0; j < towerNumber; j++) {
        if ((towers[j].getTopDisc() > smallestDisc || towers[j].getTopDisc() == 0) && towers[j].getTopDisc() != 1) {
          cout << "Moved disc " << smallestDisc << " from tower " << smallestDiscPosition << " to tower " << j << endl;
          towers[smallestDiscPosition].removeTopDisc();

          towers[j].placeDisc(smallestDisc);
          break;
        }			
      }
    }
  }


  int tmp;
  cin >> tmp;
  return 0;
}

Old Version:

// © 2017 TheFlyingKeyboard and released under MIT License
// theflyingkeyboard.net

#include <iostream>
#include <stack>
#include <vector>
#include <math.h>

using namespace std;

class Tower {
public:
  Tower(stack<int> discs) {
    _discs = discs;
  }

  Tower(int disc0) {
    _discs.push(0);
  }

  //Getters
  int getTopDisc() {
    return _discs.top();
  }

  bool placeDisc(int disc) {
    if (canPlaceDisc(disc)) {
      _discs.push(disc);

      return true;
    }

    return false;
  }

  void removeTopDisc() {
    _discs.pop();
  }

private:
  stack<int> _discs;

  bool canPlaceDisc(int disc) {
    if (_discs.top() > disc || _discs.top() == 0) {
      return true;
    }

    return false;
  }
};


int main() {
  stack<int> discs;
  vector<Tower> towers;

  const unsigned int towerNumber = 3;
  unsigned int discNumber;

  cout << "Hanoi solver iterative algorithm" << endl;
  cout << "TheFlyingKeyboard.net 2017" << endl;
  cout << "Enter number of discs: ";
  cin >> discNumber;

  discs.push(0);

  for (unsigned int i = discNumber; i > 0; i--) {
    discs.push(i);
  }

  towers.push_back(Tower(discs));

  for (unsigned int i = 0; i < towerNumber - 1; i++) {
    towers.push_back(Tower(0));
  }

  unsigned int smallestDisc;
  unsigned int smallestDiscPosition;

  for (unsigned int i = 0; i < pow(2, discNumber) - 1; i++) {
    cout << i << ". ";

    if (i % 2 == 0) {
      for (unsigned int j = 0; j < towerNumber; j++) { 
        if (towers[j].getTopDisc() == 1) { //Find smallest disc and move it to next tower 
          towers[j].removeTopDisc();
          cout << "Moved disc 1 from tower " << j << " to tower ";

          if (j == towerNumber - 1) {					
            towers[0].placeDisc(1);
            cout << "0";				
          }
          else {
            towers[j + 1].placeDisc(1);
            cout << j + 1;
          }

          cout << endl;
          
          break;
        }
      }
    }
    else { //Move smallast disc, which is not disc 1 to valid place
      smallestDisc = discNumber + 1;
      smallestDiscPosition = 0;

      for (unsigned int j = 0; j < towerNumber; j++) {
        if (towers[j].getTopDisc() < smallestDisc && towers[j].getTopDisc() != 1 && towers[j].getTopDisc() != 0) {
          smallestDisc = towers[j].getTopDisc();
          smallestDiscPosition = j;
        }
      }

      for (unsigned int j = 0; j < towerNumber; j++) {
        if ((towers[j].getTopDisc() > smallestDisc || towers[j].getTopDisc() == 0) && towers[j].getTopDisc() != 1) {
          cout << "Moved disc " << smallestDisc << " from tower " << smallestDiscPosition << " to tower " << j << endl;
          towers[smallestDiscPosition].removeTopDisc();

          towers[j].placeDisc(smallestDisc);
          break;
        }			
      }
    }
  }


  int tmp;
  cin >> tmp;
  return 0;
}

 

C++ Iterative Hanoi Solver
Tagged on:     

Leave a Reply

Your email address will not be published. Required fields are marked *