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