Tower of Hanoi Algorithm: Python, C++ Code

What is the Tower of Hanoi?

The Tower of Hanoi is a mathematical puzzle comprising three rods and a stack of disks of decreasing size placed one over the other. It is also known as the Tower of Brahma or the Lucas tower, since the French mathematician Edouard Lucas introduced it in 1883. The puzzle is based on legends about moving gold disks between three rods.

This puzzle has three rods and a variable number of stacked disks. The rods are arranged as cyclic towers, so the larger disks are stacked at the bottom and the smaller disks are stacked on top.

Initially, we are given three pegs or rods. One of them (peg A in the example) has all the disks stacked. The goal is to move the entire stack from one rod (A) to another (C) while obeying a few specific rules.

Here is the initial setup of the puzzle:

Tower of Hanoi Problem

And this is the final goal:

Rules of Tower of Hanoi

Here are the essential rules for the Tower of Hanoi:

• In the initial state of the puzzle, all disks are stacked on rod one.
• In the final state, all disks from rod one are stacked on rod two or rod three.
• Only one disk can move from one rod to another at any given time.
• Only the uppermost disk on a rod can be moved.
• A disk cannot be placed on top of a smaller disk.

The original legend was about moving 64 disks. The priests could move one disk at a time according to the rules. According to the legend, there was a prophecy that the world would end if they could complete the act. In the time complexity section, we will show that a Tower of Hanoi setting of n disks requires 2^n – 1 moves.

So, if the priests needed 1 second to move one disk, the total time to solve the puzzle would be 2^64 – 1 seconds, or roughly 584,942,417,356 years, 26 days, 7 hours, and 15 seconds.

Algorithm for Tower of Hanoi

The most common way to solve the Tower of Hanoi is a recursive algorithm. First, we pick two rods as the source and destination; the spare peg acts as the auxiliary or helper.

Here are the steps to solve the Tower of Hanoi puzzle:

• Move the top n-1 disks from the source peg to the helper peg.
• Move the nth disk from the source peg to the destination peg.
• Move the remaining n-1 disks from the helper peg to the destination peg.

Note: If we have a single disk, we can move it directly from source to destination.

How to solve Tower of Hanoi Puzzle

Let us illustrate the algorithm for three disks. Consider peg A as the source, peg B as the helper, and peg C as the destination.

Step 1) Initially, all the disks are stacked on peg A.

At this stage: Source = Peg A, Destination = Peg C, Helper = Peg B.

Now, we need to move the top n-1 disks from the source to the helper.

Note: Although we can only move one disk at a time, this step reduces our 3-disk problem to a 2-disk problem, which is handled by a recursive call.

Step 2) As we make a recursive call from peg A with peg B as the destination, we use peg C as the helper.

Notice that we are back at stage one for the same Tower of Hanoi problem, but now for two disks. We move n-1 (that is, one) disk from source to helper, which moves the smallest disk from peg A to peg C.

At this stage: Source = peg A, Destination = peg B, Helper = peg C.

Step 3) According to the algorithm, the nth (2nd) disk is now transferred to the destination, peg B.

At this stage: Source = peg A, Destination = peg B, Helper = peg C.

Step 4) Now, we move the n-1 disk (disk one) from helper peg C to destination peg B, following the third stage of the algorithm.

At this stage: Source = peg A, Destination = peg B, Helper = peg C.

Step 5) After completing the recursive call, we return to our previous setting at the first stage of the algorithm.

Step 6) In the second stage, we move disk 3 from source peg A to destination peg C.

At this stage: Source = peg A, Destination = peg C, Helper = peg B.

Step 7) The next task is to move the remaining disks from helper (peg B) to destination (peg C). We will use the original source (peg A) as the helper this time.

Step 8) Since we cannot move two disks at once, we make a recursive call for disk 1. According to our algorithm, the destination in this step is peg A.

At this stage: Source = peg B, Destination = peg A, Helper = peg C.

Step 9) Our recursive call is complete. We now move disk 2 from its source to its destination.

At this stage: Source = peg B, Destination = peg C, Helper = peg A.

Step 10) We finish by moving the remaining n-1 disk (disk 1) from helper to destination.

At this stage: Source = peg A, Destination = peg C, Helper = peg B.

Pseudo Code for Tower of Hanoi

START
Procedure Tower_Of_Hanoi(disk, source, dest, helper)
    IF disk == 1 THEN
        move disk from source to dest
    ELSE
        Tower_Of_Hanoi(disk - 1, source, helper, dest)
        move disk from source to dest
        Tower_Of_Hanoi(disk - 1, helper, dest, source)
    END IF
END Procedure

Program code in C++

#include <bits/stdc++.h>
using namespace std;
void tower_of_hanoi(int num, string source, string dest, string helper) {
    if (num == 1) {
        cout << " Move disk 1 from tower " << source << " to tower " << dest << endl;
        return;
    }
    tower_of_hanoi(num - 1, source, helper, dest);
    cout << " Move disk " << num << " from tower " << source << " to tower " << dest << endl;
    tower_of_hanoi(num - 1, helper, dest, source);
}
int main() {
    int num;
    cin >> num;
    printf("The sequence of moves :\n");
    tower_of_hanoi(num, "I", "III", "II");
    return 0;
}

Output:

3
The sequence of moves :
Move disk 1 from tower I to tower III
Move disk 2 from tower I to tower II
Move disk 1 from tower III to tower II
Move disk 3 from tower I to tower III
Move disk 1 from tower II to tower I
Move disk 2 from tower II to tower III
Move disk 1 from tower I to tower III

Program code in Python

def tower_of_hanoi(n, source, destination, helper):
    if n == 1:
        print("Move disk 1 from peg", source, "to peg", destination)
        return
    tower_of_hanoi(n - 1, source, helper, destination)
    print("Move disk", n, "from peg", source, "to peg", destination)
    tower_of_hanoi(n - 1, helper, destination, source)
# n = number of disks
n = 3
tower_of_hanoi(n, 'A', 'B', 'C')

Output:

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

Complexity of Tower of Hanoi

Here are the time and space complexity of the Tower of Hanoi:

1) Time complexity:

Looking back at the algorithm, we make a recursive call for (n-1) disks twice per call. Each (n-1) recursion breaks down into ((n-1)-1) recursions, and so on, until we reach the single-disk base case.

For three disks:

• Disk 3 calls the recursive function for disk 2 twice.
• Disk 2 calls the recursive function for disk 1 twice.
• Disk 1 moves in constant time, giving the time to solve for three disks.

Expressed as a recurrence:

= 2 × (Time to solve for two disks) + constant time to move disk 3

= 2 × (2 × time to solve for one disk + constant time to move disk 2) + constant time to move disk 3

= (2 × 2) × constant time to move disk 1 + 2 × constant time to move disk 2 + constant time to move disk 3

For n disks, this becomes:

2^n-1 × constant time to move disk 1 + 2^n-2 × constant time to move disk 2 + ….

This geometric progression sums to O(2ⁿ – 1), which simplifies to O(2ⁿ), an exponential time complexity.

2) Space complexity:

The space complexity of the Tower of Hanoi is O(n). The recursion uses the call stack, and the maximum depth of the stack equals n, the number of disks. That is why the space complexity is O(n).

FAQs