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