# Tower of Hanoi

An interesting game right?

If you don't know about this game, take a look here,

{% embed url="<https://www.mathsisfun.com/games/towerofhanoi.html>" %}
just play and learn
{% endembed %}

So to solve it (displaying the steps), carefully analyze what actually happens when you have one and two disks. Then try to recreate the scenario with 3 disks. Maybe you can find a recursive approach here, here's the code,

## 6.9 Tower of Hanoi (Recursion)

```cpp
#include<iostream>
using namespace std;

void towerOfHanoi(int n, char beg, char aux, char end) {
    if (n==1) {
        cout << beg << " -> " << end << "\n";
        return;
    }
    towerOfHanoi(n-1, beg, end, aux);
    towerOfHanoi(1, beg, aux, end);
    towerOfHanoi(n-1, aux, beg, end);
}

int main() {
    towerOfHanoi(4, 'A', 'B', 'C');
}
```

So, with recursion it's too short and feels simple right?

It's not this simple if you want to apply this thing with stack instead of recusion. A bit of trial and error perhaps?

## 6.10 Tower of Hanoi (Stack)

It's the iterative approach of the above code with stack,

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

void towerOfHanoi(int n, char beg, char aux, char end) {
    int add = 2;
    stack<char> st_beg, st_aux, st_end;
    stack<int> st_n, st_add;
    
    while (true) {
        if (n == 1) {
            cout << beg << " -> " << end << "\n";
            add = 5;
        }
        if (add == 2) {
            st_beg.push(beg), st_aux.push(aux), st_end.push(end);
            st_n.push(n), st_add.push(3);
            beg = st_beg.top();
            aux = st_end.top();
            end = st_aux.top();
            n--;
        }
        if (add == 3) {
            cout << beg << " -> " << end << "\n";
            st_beg.push(beg), st_aux.push(aux), st_end.push(end);
            st_n.push(n), st_add.push(5);
            beg = st_aux.top();
            aux = st_beg.top();
            end = st_end.top();
            n--;
            add = 2;
        }
        if (add == 5) {
            if (st_beg.empty()) return;
            beg = st_beg.top();
            aux = st_aux.top();
            end = st_end.top();
            n = st_n.top();
            add = st_add.top();
            st_beg.pop(), st_aux.pop(), st_end.pop(); 
            st_add.pop(), st_n.pop();
        }
    }
}

int main() {
    towerOfHanoi(3, 'A', 'B', 'C');
}
```

Or, perhaps one even more minimal approach? (Taught to me by **MH Nazmul**)

```cpp
#include <bits/stdc++.h>
using namespace std;

void hanoi_stack(int n, char beg, char aux, char end) {
    stack<pair<int, vector<char>>> st;
    st.push({n, {beg, aux, end}});

    while (!st.empty()) {
        int n = st.top().first;
        char beg = st.top().second[0];
        char aux = st.top().second[1];
        char end = st.top().second[2];
        st.pop();
        if (n == 1) {
            cout << beg << " -> " << end << endl;
        } else {
            st.push({n-1, {aux, beg, end}});
            st.push({1, {beg, aux, end}});
            st.push({n-1, {beg, end, aux}});
        }
    }
}

int main() {
    hanoi_stack(3, 'A', 'B', 'C');
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://sharafat.gitbook.io/dsa/structures/stack/tower-of-hanoi.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.