C++ iterative 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 *

By continuing to use the site, you agree to the use of cookies. You can read more about it the Cookies&Privacy Policy Section Above. more information

The cookie settings on this website are set to "allow cookies" to give you the best browsing experience possible. If you continue to use this website without changing your cookie settings or you click "Accept" below then you are consenting to this. You can read more about it the Cookies&Privacy Policy Section.

Close