TOWER OF HANOI-ALGORITHM

The Tower of Hanoi problem is a well-known mathematical and algorithmic puzzle from the field of recursion and combinatorics.

The problem consists of three rods: A, B, and C. On rod A, disks are stacked so that the largest disk is at the bottom, followed by a smaller one on top, then an even smaller one, and so on. In other words, if we consider the diameters of the disks as numbers from bottom to top, this sequence is in decreasing order.

The goal of this "game" is to move all disks onto rod C, using rod B as an auxiliary, while respecting the following rules:

Only one disk can be moved at a time.
A larger disk may never be placed on top of a smaller disk.

This problem is usually solved recursively:

If there is only 1 disk, simply move it from A to C.
If there are n disks:
1. Move n-1 disks from A to B (using C as auxiliary).
2. Move the largest disk from A to C.
3. Move n-1 disks from B to C (using A as auxiliary).

The algorithm can be solved using recursion.

Let us observe the initial state of the disks and rods in Figure 1. On rod A, there are n disks (in the figure n = 6), arranged from the largest (in diameter) at the bottom to the smallest at the top. Therefore, the smallest disk is always placed on top.

The goal is to transfer all these disks to rod C in the same order. The movement of the disks is restricted by the condition that a larger disk may never be placed on top of a smaller one.

We use the auxiliary rod B to temporarily place some of the disks there, in order to free the larger disk and move it to the destination rod C.

Figure 1: The "Towers of Hanoi" problem - initial state

If we were to create a function that should print which disk is being moved from which (source) to which (destination) and via which (auxiliary), it would look like this:

tower_of_hanoi(int n, string from, string to, string helper)

It should be noted here that the problem can be solved by reducing it to the recursive repetition of the following: In order to place the largest disk (let’s denote it as the n-th) onto the target peg (peg C), the remaining smaller disks must first be moved away, that is, the disks from position n-1 down to 1 (see Figure 2).

In the example shown in Figure 2, the transfer of the top 4 disks is illustrated, i.e., from n-2 down to 1 (from the dashed line in Figure 2). For the remaining two largest disks (the blue ones in Figure 2), the procedure would be repeated in a similar way.

We can consider the largest disk of the moving stack as the yellow disk. This disk must be placed first onto peg C. To achieve this, the other disks need to be temporarily moved to the auxiliary peg B.

Figure 2: Initial movement of a stack of 4 disks from above

Therefore, the task that the recursive function needs to perform can be reduced to the following steps:

Move the stack of disks that are above the current largest disk (initially, this is the n-th disk) to the auxiliary peg B (see Figure 3).
Move the current largest disk (initially the absolute largest, and as the stack decreases, the currently largest) directly onto peg C (see Figure 4).
Move the remaining disks from peg B to peg C (see Figure 5).

Figure 3: Moving the 3 smaller discs from above from A to the auxiliary rack B

Step 1: Moving the 3 smaller disks to rack B

What is important in step 1, that is, when moving the stack of three smaller disks, is that this move cannot be done "all at once," nor can the disks be moved directly one by one onto peg B. This is because it must never happen that a larger disk is placed on top of a smaller one. Instead, the same recursion is applied—that is, the same procedure of steps 1, 2, and 3, but with one level of recursion less. For example, if at the beginning there were n = 4, now the largest remaining disk will be at the level n = 3. This process is repeated recursively until all disks are placed on peg B.

If we were to run the program, this described step would be broken down into the following sub-steps:

Move disk 1 from A to B
Move disk 2 from A to C
Move disk 1 from B to C
Move disk 3 from A to B
Move disk 1 from C to A
Move disk 2 from C to B
Move disk 1 from A to B

Disk 1 is the smallest in this stack, while disk 3 is the largest.

Figure 4: Moving the currently largest disk directly to rack C

Step 2: Move the currently largest disk directly to rack C

Once the stack of three disks has been moved to peg B, disk 4 can now be directly transferred from peg A to peg C.

In the running program, this would correspond to the following output:

Move disk 4 from A to C

Moving the rest of the disks from B to C

Moving the remaining stack of 3 disks from the auxiliary peg B to the destination peg C also cannot be done in a single step, but requires further use of the same recursion, with the source, destination, and auxiliary pegs swapped. Let’s look at the continuation of the program execution that describes this process (see Figure 5):

Moving disk 1 from B to C
Moving disk 2 from B to A
Moving disk 1 from C to A
Moving disk 3 from B to C
Moving disk 1 from A to B
Moving disk 2 from A to C
Moving disk 1 from B to C

Figure 5: Moving 3 smaller disks from auxiliary rack B to destination rack C

From this, we can conclude what the code should look like: A recursive function should be created that takes as parameters the labels (letters) of the source, destination, and auxiliary pegs, as well as the recursion level n.

The function first checks the current recursion level, and if it is zero, it performs a backtrack (returns). If it is not zero, the function calls itself recursively, decreasing the recursion level by 1 each time. This corresponds to Step 1, where the n−1 smaller disks are moved from peg A to the auxiliary peg B.

Then, the function prints the instruction at the current recursion level. This corresponds to Step 2, i.e., moving the bottom disk from peg A to the destination peg C.

Finally, another recursive call is made to perform Step 3, which corresponds to moving the stack of disks from peg B to peg C.

Iz ovoga možemo zaključiti kako bi trebalo da izgleda kod: Napraviti rekurzivnu funkciju, koja za parametre prima tekst(slovo) izvornog, odredišnog i pomoćnog stuba kao i nivo rekurzije n. Sama funkcija prvo proverava trenutni nivo rekurzije i ako je nula, izaziva vraćanje unazad. Ako nije nula poziva se rekurzija (ista funkcija) koja će da napravi niz poziva smanjujući nivo rekurzije svaki put za 1, a to odgovara postupku 1, gde se 3 manja diska premeštaju sa stalka A na pomoćni stalak B.
Zatim se ispisuje tekst u trenutnom nivou rekurzije. To odgovara postupku 2, tj. Premeštanje donjeg diska sa A na odredišni stalak C.
I na kraju još jedan rekurzivni poziv koji će izvršiti postupak 3, odnosno premeštanje gomile diskova sa B na C.

#include <iostream>
using namespace std;

// Function that recursively solves the Tower of Hanoi problem
// n       – number of disks to move
// from    – name of the source peg
// to      – name of the target peg
// helper  – name of the auxiliary peg
void tower_of_hanoi(int n, string from, string to, string helper) {
    // Base case: if there are no disks, no moves are needed
    if (n == 0) {
        return;
    }

    // 1. Move n-1 disks from "from" peg to "helper" peg
    //    Use "to" peg as auxiliary
    tower_of_hanoi(n - 1, from, helper, to);

    // 2. Move the largest (n-th) disk from "from" peg to "to" peg
    cout << "Moving disk " << n
         << " from " << from
         << " to " << to << endl;

    // 3. Move n-1 disks from "helper" peg to "to" peg
    //    Use "from" peg as auxiliary
    tower_of_hanoi(n - 1, helper, to, from);
}

int main() {
    int n;
    cout << "Enter the number of disks: ";
    cin >> n;

    // Run the algorithm – we want to move all disks from A to C
    // using B as auxiliary peg
    tower_of_hanoi(n, "A", "C", "B");

    return 0;
}

Tower of Hanoi Problem – Example and Explanation

Sample Input:

Sample Output:

Moving disk 1 from A to B
Moving disk 2 from A to C
Moving disk 1 from B to C
Moving disk 3 from A to B
Moving disk 1 from C to A
Moving disk 2 from C to B
Moving disk 1 from A to B
Moving disk 4 from A to C
Moving disk 1 from B to C
Moving disk 2 from B to A
Moving disk 1 from C to A
Moving disk 3 from B to C
Moving disk 1 from A to B
Moving disk 2 from A to C
Moving disk 1 from B to C

Code Explanation

The algorithm uses recursion and is based on three steps:

Move n−1 disks from the source peg (A) to the auxiliary peg (B).
Move the largest disk (n-th) from the source peg (A) to the target peg (C).
Move n−1 disks from the auxiliary peg (B) to the target peg (C).

These steps are repeated recursively until only one disk remains, which is the base case of the recursion.

Constraints / Complexity

The number of moves required to solve the problem with n disks is:

P(n) = 2^n − 1

This means that the number of moves grows exponentially with the number of disks:

n = 3 → 7 moves
n = 4 → 15 moves
n = 10 → 1023 moves
n = 20 → over one million moves

Therefore, the problem is mainly used as an illustration of recursion and an academic example, while solving it for large values of n is practically infeasible.

Previous
|< Recursive Algorithms